Distinct Numbers

Problem Overview

Learning Goals

• Use hash sets to track unique elements efficiently
• Apply sorting to group duplicates for counting
• Understand time-space tradeoffs between approaches

Problem Statement

Given n integers, count how many distinct values exist in the array.

Input:

• Line 1: Integer n (number of elements)
• Line 2: n integers separated by spaces

Output:

• One integer: the count of distinct values

Example:

Input:
5
2 3 2 2 3

Output:
2

The values are 2 and 3, so the answer is 2.

Constraints:

• 1 <= n <= 2 x 10^5
• 1 <= x_i <= 10^9

Approach 1: Hash Set

Idea: Add all elements to a set. The set automatically handles duplicates.

Time Complexity: O(n) average Space Complexity: O(n)

Python

def count_distinct_set(arr):
  return len(set(arr))

# Full solution with input
n = int(input())
arr = list(map(int, input().split()))
print(len(set(arr)))

Approach 2: Sorting

Idea: Sort the array. After sorting, duplicates are adjacent. Count positions where arr[i] != arr[i-1].

Time Complexity: O(n log n) Space Complexity: O(1) if sorting in-place

Python

def count_distinct_sort(arr):
  if not arr:
    return 0
  arr.sort()
  count = 1  # First element is always distinct
  for i in range(1, len(arr)):
    if arr[i] != arr[i-1]:
      count += 1
  return count

# Full solution with input
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 1
for i in range(1, n):
  if arr[i] != arr[i-1]:
    count += 1
print(count)

Comparison: When to Use Which?

Practical Notes:

• Set approach is simpler and faster on average
• Sorting approach uses less memory
• For CSES constraints (n <= 2 x 10^5), both approaches work well

Common Mistakes

1. Forgetting the first element in sorting approach: ```python

   WRONG: starts count at 0

   count = 0 for i in range(1, n): if arr[i] != arr[i-1]: count += 1

CORRECT: starts count at 1 (first element is always distinct)

count = 1 for i in range(1, n): if arr[i] != arr[i-1]: count += 1

2. **Off-by-one in loop bounds:**
   ```python
# WRONG: will cause index error
for i in range(n):
  if arr[i] != arr[i-1]:  # arr[-1] when i=0!

# CORRECT: start from index 1
for i in range(1, n):
  if arr[i] != arr[i-1]:

1. Empty array edge case: Always check if array is empty before processing.

Related Problems