CSES - Distinct Numbers

Authors: Andrew Wang, Maggie Liu

Edit This Page

Method 1 - Sorting

Sort the array of numbers. Loop through the array and increment the answer for every distinct number. Distinct numbers can be found if the current number isn't equal to the previous number in the array.

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N\log{N})

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	int N;
	cin >> N;
	vector<int> arr(N);
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr.begin(), arr.end());
	int ans = 1;

Java

import java.io.*;
import java.util.*;


public class DistinctNumbers {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); }

Python

n = int(input())
# create a sorted list of the numbers
numbers = sorted(map(int, input().split()))
ans = 1
for i in range(1, n):
	# if the current number is different from the previous
	# it is a distinct number so we add 1 to the answer
	if numbers[i] != numbers[i - 1]:
		ans += 1
print(ans)

Method 2 - Sets

See this module.

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum