Open In App

Count Distinct ( Unique ) elements in an array

Last Updated : 12 Jun, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given an array arr[] of length N, The task is to count all distinct elements in arr[].

Examples: 

Input: arr[] = {10, 20, 20, 10, 30, 10}
Output: 3
Explanation: There are three distinct elements 10, 20, and 30.

Input: arr[] = {10, 20, 20, 10, 20}
Output: 2

Naïve Approach:

Create a count variable and run two loops, one with counter i from 0 to N-1 to traverse arr[] and second with counter j from 0 to i-1 to check if ith element has appeared before. If yes, increment the count. 

Below is the Implementation of the above approach.

C++ 
// C++ program to count distinct elements
// in a given array
#include <iostream>
using namespace std;

int countDistinct(int arr[], int n)
{
    int res = 1;

    // Pick all elements one by one
    for (int i = 1; i < n; i++) {
        int j = 0;
        for (j = 0; j < i; j++)
            if (arr[i] == arr[j])
                break;

        // If not printed earlier, then print it
        if (i == j)
            res++;
    }
    return res;
}

// Driver program to test above function
int main()
{
    int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countDistinct(arr, n);
    return 0;
}
Java 
// Java program to count distinct
// elements in a given array

import java.io.*;

class GFG {

    static int countDistinct(int arr[], int n)
    {
        int res = 1;

        // Pick all elements one by one
        for (int i = 1; i < n; i++) {
            int j = 0;
            for (j = 0; j < i; j++)
                if (arr[i] == arr[j])
                    break;

            // If not printed earlier,
            // then print it
            if (i == j)
                res++;
        }
        return res;
    }

    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
        int n = arr.length;
        System.out.println(countDistinct(arr, n));
    }
}

// This code is contributed by Code_Mech.
Python 
# Python3 program to count distinct
# elements in a given array


def countDistinct(arr, n):

    res = 1

    # Pick all elements one by one
    for i in range(1, n):
        j = 0
        for j in range(i):
            if (arr[i] == arr[j]):
                break

        # If not printed earlier, then print it
        if (i == j + 1):
            res += 1

    return res


# Driver Code
arr = [12, 10, 9, 45, 2, 10, 10, 45]
n = len(arr)
print(countDistinct(arr, n))

# This code is contributed by Mohit Kumar
C# 
// C# program to count distinct
// elements in a given array
using System;

class GFG {

    static int countDistinct(int[] arr, int n)
    {
        int res = 1;

        // Pick all elements one by one
        for (int i = 1; i < n; i++) {
            int j = 0;
            for (j = 0; j < i; j++)
                if (arr[i] == arr[j])
                    break;

            // If not printed earlier,
            // then print it
            if (i == j)
                res++;
        }
        return res;
    }

    // Driver code
    public static void Main()
    {
        int[] arr = { 12, 10, 9, 45, 2, 10, 10, 45 };
        int n = arr.Length;
        Console.WriteLine(countDistinct(arr, n));
    }
}

// This code is contributed
// by Akanksha Rai
Javascript 
<script>

// JavaScript program to count distinct elements 
// in a given array 

function countDistinct(arr, n) 
{ 
    let res = 1; 

    // Pick all elements one by one 
    for (let i = 1; i < n; i++) { 
        let j = 0; 
        for (j = 0; j < i; j++) 
            if (arr[i] === arr[j]) 
                break; 

        // If not printed earlier, then print it 
        if (i === j) 
            res++; 
    } 
    return res; 
} 

// Driver program to test above function 
    let arr = [ 12, 10, 9, 45, 2, 10, 10, 45 ]; 
    let n = arr.length; 
    document.write(countDistinct(arr, n)); 


// This code is contributed by Surbhi Tyagi

</script>
PHP 
<?php
// PHP program to count distinct elements
// in a given array
function countDistinct( &$arr, $n)
{
    $res = 1;

    // Pick all elements one by one
    for ( $i = 1; $i < $n; $i++)
    {

        for ($j = 0; $j < $i; $j++)
            if ($arr[$i] == $arr[$j])
                break;

        // If not printed earlier,
        // then print it
        if ($i == $j)
            $res++;
    }
    return $res;
}

// Driver Code
$arr = array( 12, 10, 9, 45, 2, 10, 10, 45 );
$n = count($arr);
echo countDistinct($arr, $n);

// This code is contributed by
// Rajput-Ji 
?>

Output
5

Time Complexity: O(n2)
Auxiliary Space: O(1)

Using sorting:

Below is the idea to solve the problem:

Sort the array so that all occurrences of every element become consecutive. Once the occurrences become consecutive, then traverse the sorted array and count distinct elements by comparing the consecutive elements.

Follow the steps below to Implement the idea:

  • Initialize a res variable with 0 and sort arr[].
  • Run a for loop from 0 to N-1.
    • While i is less than N-1 and arr[i] is equal to arr[i+1] increment i.
    • increment res by one. 
  • Return res. 

Below is the implementation of above approach that is as follows: 

C++ 
// C++ program to count all distinct elements
// in a given array

#include <algorithm>
#include <iostream>

using namespace std;

int countDistinct(int arr[], int n)
{
    // First sort the array so that all
    // occurrences become consecutive
    sort(arr, arr + n);

    // Traverse the sorted array
    int res = 0;
    for (int i = 0; i < n; i++) {

        // Move the index ahead while
        // there are duplicates
        while (i < n - 1 && arr[i] == arr[i + 1])
            i++;

        res++;
    }

    return res;
}

// Driver program to test above function
int main()
{
    int arr[] = { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countDistinct(arr, n);
    return 0;
}
Java 
// Java program to count all distinct elements
// in a given array
import java.util.Arrays;

class GFG {

    static int countDistinct(int arr[], int n)
    {
        // First sort the array so that all
        // occurrences become consecutive
        Arrays.sort(arr);

        // Traverse the sorted array
        int res = 0;
        for (int i = 0; i < n; i++) {

            // Move the index ahead while
            // there are duplicates
            while (i < n - 1 && arr[i] == arr[i + 1]) {
                i++;
            }
            res++;
        }
        return res;
    }

    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
        int n = arr.length;
        System.out.println(countDistinct(arr, n));
    }
}

// This code is contributed by 29AjayKumar
Python 
# Python3 program to count all distinct
# elements in a given array


def countDistinct(arr, n):

    # First sort the array so that all
    # occurrences become consecutive
    arr.sort()

    # Traverse the sorted array
    res = 0
    i = 0
    while(i < n):

        # Move the index ahead while
        # there are duplicates
        while (i < n - 1 and
               arr[i] == arr[i + 1]):
            i += 1

        res += 1
        i += 1

    return res


# Driver Code
arr = [6, 10, 5, 4, 9, 120, 4, 6, 10]
n = len(arr)
print(countDistinct(arr, n))

# This code is contributed by mits
C# 
// C# program to count all distinct elements
// in a given array
using System;

class GFG {

    static int countDistinct(int[] arr, int n)
    {
        // First sort the array so that all
        // occurrences become consecutive
        Array.Sort(arr);

        // Traverse the sorted array
        int res = 0;
        for (int i = 0; i < n; i++) {

            // Move the index ahead while
            // there are duplicates
            while (i < n - 1 && arr[i] == arr[i + 1]) {
                i++;
            }
            res++;
        }
        return res;
    }

    // Driver code
    public static void Main()
    {
        int[] arr = { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
        int n = arr.Length;
        Console.WriteLine(countDistinct(arr, n));
    }
}

// This code is contributed by Code_Mech.
Javascript 
<script>

// JavaScript program to count all distinct elements
// in a given array

function countDistinct(arr,n)
{
    // First sort the array so that all
        // occurrences become consecutive
        arr.sort(function(a,b){return a-b;});
 
        // Traverse the sorted array
        let res = 0;
        for (let i = 0; i < n; i++)
        {
 
            // Move the index ahead while
            // there are duplicates
            while (i < n - 1 &&
                    arr[i] == arr[i + 1])
            {
                i++;
            }
            res++;
        }
        return res;
}

// Driver code
let arr=[6, 10, 5, 4, 9, 120, 4, 6, 10];
let n = arr.length;
document.write(countDistinct(arr, n));


// This code is contributed by unknown2108

</script>
PHP 
<?php
// PHP program to count all distinct
// elements in a given array

function countDistinct($arr, $n)
{
    // First sort the array so that all
    // occurrences become consecutive
    sort($arr, 0);

    // Traverse the sorted array
    $res = 0;
    for ($i = 0; $i < $n; $i++)
    {

        // Move the index ahead while
        // there are duplicates
        while ($i < $n - 1 && 
               $arr[$i] == $arr[$i + 1])
            $i++;

        $res++;
    }

    return $res;
}

// Driver Code
$arr = array( 6, 10, 5, 4, 9, 120, 4, 6, 10 );
$n = sizeof($arr);
echo countDistinct($arr, $n);

// This code is contributed by Akanksha Rai
?>

Output
6

Time Complexity: O(n logn)
Auxiliary Space: O(1)

Using Hashing:

The idea is to traverse the given array from left to right and keep track of visited elements in a hash set , as a set consists of only unique elements. 

Follow the steps below to implement the idea:

  1. Create an unordered_set s and a variable res initialized with 0.
  2. Run a for loop from 0 to N-1 
    • If the current element is not present in s, insert it in s increment res by 1. 
  3. Return res.

Below is the implementation of the above approach.

C++ 
/* CPP program to print all distinct elements
   of a given array */
#include <bits/stdc++.h>
using namespace std;

// This function prints all distinct elements
int countDistinct(int arr[], int n)
{
    // Creates an empty hashset
    unordered_set<int> s;

    // Traverse the input array
    int res = 0;
    for (int i = 0; i < n; i++) {

        // If not present, then put it in
        // hashtable and increment result
        if (s.find(arr[i]) == s.end()) {
            s.insert(arr[i]);
            res++;
        }
    }

    return res;
}

// Driver Code
int main()
{
    int arr[] = { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countDistinct(arr, n);
    return 0;
}
Java 
// Java Program to count
// Unique elements in Array
import java.util.*;

class GFG {

    // This method returns count
    // of Unique elements
    public static int countDistinct(int arr[], int n)
    {

        HashSet<Integer> hs = new HashSet<Integer>();

        for (int i = 0; i < n; i++) {
            // add all the elements to the HashSet
            hs.add(arr[i]);
        }

        // return the size of hashset as
        // it consists of all Unique elements
        return hs.size();
    }

    // Driver code
    public static void main(String[] args)
    {
        int arr[]
            = new int[] { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
        System.out.println(countDistinct(arr, arr.length));
    }
}

// This code is contributed by Adarsh_Verma
Python 
''' Python3 program to print all distinct elements 
of a given array '''

# This function prints all distinct elements


def countDistinct(arr, n):

    # Creates an empty hashset
    s = set()

    # Traverse the input array
    res = 0
    for i in range(n):

        # If not present, then put it in
        # hashtable and increment result
        if (arr[i] not in s):
            s.add(arr[i])
            res += 1

    return res


# Driver code
arr = [6, 10, 5, 4, 9, 120, 4, 6, 10]
n = len(arr)
print(countDistinct(arr, n))

# This code is contributed by SHUBHAMSINGH10
C# 
// C# Program to count
// Unique elements in Array
using System;
using System.Collections.Generic;

class GFG {

    // This method returns count
    // of Unique elements
    public static int countDistinct(int[] arr, int n)
    {

        HashSet<int> hs = new HashSet<int>();

        for (int i = 0; i < n; i++) {
            // add all the elements to the HashSet
            hs.Add(arr[i]);
        }

        // return the size of hashset as
        // it consists of all Unique elements
        return hs.Count;
    }

    // Driver code
    public static void Main()
    {
        int[] arr
            = new int[] { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
        Console.WriteLine(countDistinct(arr, arr.Length));
    }
}

/* This code contributed by PrinciRaj1992 */
Javascript 
<script>
// Javascript Program to count
// Unique elements in Array

// This method returns count
    // of Unique elements
function countDistinct(arr,n)
{
    let hs = new Set();
 
        for(let i = 0; i < n; i++)
        {
            // add all the elements to the HashSet
            hs.add(arr[i]);
        }
         
        // return the size of hashset as
        // it consists of all Unique elements
        return hs.size;    
}

// Driver code
let arr=[6, 10, 5, 4, 9,120, 4, 6, 10];
document.write(countDistinct(arr,arr.length));
                                


// This code is contributed by patel2127
</script>
PHP 
<?php
// PHP program to print all distinct elements 
// of a given array 

// This function prints all distinct elements
function countDistinct($arr, $n)
{
    // Creates an empty hashset
    $s = array();

    // Traverse the input array
    $res = 0;
    for ($i = 0; $i < $n; $i++) 
    {
        // If not present, then put it in
        // hashtable and increment result
        array_push($s,$arr[$i]);
    }
    $s = array_unique($s);
    return count($s);
}

// Driver Code
$arr = array( 6, 10, 5, 4, 9, 120, 4, 6, 10 );
$n = count($arr);
echo countDistinct($arr, $n);

// This code is contributed by mits
?>

Output
6

Time complexity: O(n)
Auxiliary Space: O(n), since n extra space has been taken.

Using Set STL:

Iterate over all the elements of the array insert them in an unordered set. As the set only contains distinct elements, so the size of set will be the answer.

Follow the below steps to Implement the idea:

  • Insert all the elements into the set S one by one.
  • Store the total size s of the set using set::size().
  • The total size s is the number of distinct elements present in the array.

Below is the Implementation of above approach.

C++ 
#include <bits/stdc++.h>
using namespace std;
// function that accepts the array and it's size and returns
// the number of distince elements
int distinct(int* arr, int len)
{

    // declaring a set container using STL
    set<int> S;
    for (int i = 0; i < len; i++) {

        // inserting all elements of the
        // array into set
        S.insert(arr[i]);
    }
    // calculating the size of the set
    int ans = S.size();
    return ans;
}
int main()
{
    int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
    // calculating the size of the array
    int l = sizeof(arr) / sizeof(int);
    // calling the function on array
    int dis_elements = distinct(arr, l);
    cout << dis_elements << endl;
    return 0;
}
Java 
import java.util.*;
class GFG {

    // function that accepts
    // the array and it's size and
    // returns the number of distince elements
    static int distinct(int[] arr, int len)
    {
        // declaring a set container
        // using STL
        HashSet<Integer> S = new HashSet<>();

        for (int i = 0; i < len; i++) {
            // inserting all elements of the
            // array into set
            S.add(arr[i]);
        }

        // calculating the size of the set
        int ans = S.size();
        return ans;
    }

    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };

        // calculating the size of the
        // array
        int l = arr.length;
        // calling the function on array
        int dis_elements = distinct(arr, l);
        System.out.print(dis_elements + "\n");
    }
}

// This code is contributed by Rajput-Ji
Python 
# function that accepts the array and it's size and returns
# the number of distince elements


def distinct(arr, l):
    # declaring a set container using STL
    S = set()
    for i in range(l):
        # inserting all elements of the
        # array into set
        S.add(arr[i])

    # calculating the size of the set
    ans = len(S)
    return ans


# Driver code
if __name__ == '__main__':
    arr = [12, 10, 9, 45, 2, 10, 10, 45]

    # calculating the size of the array
    l = len(arr)

    # calling the function on array
    dis_elements = distinct(arr, l)
    print(dis_elements, "")

# This code is contributed by Rajput-Ji
C# 
using System;
using System.Collections.Generic;

public class GFG {

    // function that accepts the array and it's size and
    // returns the number of distince elements
    static int distinct(int[] arr, int len)
    {
        // declaring a set
        // container using STL
        HashSet<int> S = new HashSet<int>();
        for (int i = 0; i < len; i++) {
            // inserting all elements of the
            // array into set
            S.Add(arr[i]);
        }
        // calculating the size of the set
        int ans = S.Count;
        return ans;
    }

    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { 12, 10, 9, 45, 2, 10, 10, 45 };

        // calculating the size of the array
        int l = arr.Length;

        // calling the function on array
        int dis_elements = distinct(arr, l);
        Console.Write(dis_elements + "\n");
    }
}

// This code is contributed by Rajput-Ji
Javascript 
<script>
    // function that accepts the array and it's size and returns
    // the number of distince elements
    function distinct(arr , len)
    {
        var S = new Set(); // declaring a set container using STL
        var i =0;
        for (i = 0; i < len; i++)
        {
            S.add(arr[i]); // inserting all elements of the
            // array into set
        }
        var ans = S.size; // calculating the size of the set
        return ans;
    }

    // Driver code
        var arr = [ 12, 10, 9, 45, 2, 10, 10, 45 ];
        var l = arr.length; // calculating the size of the array
        var dis_elements = distinct(arr, l); // calling the function on array
        document.write(dis_elements);

// This code is contributed by Rajput-Ji.
</script>

Output
5

One-liner Code –

Python 
arr = [12, 10, 9, 45, 2, 10, 10, 45]
print(len(set(arr)))
Javascript 
let arr = [12, 10, 9, 45, 2, 10, 10, 45]
console.log((new Set(arr)).size)

Output
5



author
kartik
Improve
Next Article
Count distinct elements in an array in Python

Similar Reads

Maximize count of unique array elements by incrementing array elements by K
Given an array arr[] consisting of N integers and an integer K, the task is to find the maximum number of unique elements possible by increasing any array element by K only once. Examples: Input: arr[] = {0, 2, 4, 3, 4}, K = 1Output: 5Explanation:Increase arr[2] ( = 4) by K ( = 1). Therefore, new array is {0, 2, 4, 3, 5} which has 5 unique elements
8 min read
k-th distinct (or non-repeating) element among unique elements in an array.
Given an integer array, print k-th distinct element in an array. The given array may contain duplicates and the output should print k-th element among all unique elements. If k is more than number of distinct elements, print -1.Examples : Input : arr[] = {1, 2, 1, 3, 4, 2}, k = 2 Output : 4 First non-repeating element is 3 Second non-repeating elem
9 min read
Print all Distinct ( Unique ) Elements in given Array
Given an integer array, print all distinct elements in an array. The given array may contain duplicates and the output should print every element only once. The given array is not sorted. Examples: Input: arr[] = {12, 10, 9, 45, 2, 10, 10, 45}Output: 12, 10, 9, 45, 2 Input: arr[] = {1, 2, 3, 4, 5}Output: 1, 2, 3, 4, 5 Input: arr[] = {1, 1, 1, 1, 1}
13 min read
Maximize count of unique elements in Array by changing elements to negative
Given array arr containing N integers. the task is to find the maximum number of unique elements in the array if each element in the array can be changed to its negative i.e. X can be changed to -X in the array. Example: Input: arr[] = {-1, 3, 2, 3, 2}Output: 5Explanation: Change one 2 to -2 and another 3 to -3 to get the arr[]={-1, 3, 2, -3, -2},
5 min read
Count distinct elements after adding each element of First Array with Second Array
Given two arrays arr1[] and arr2[]. We can generate another array arr3[] by adding each element of the array arr1[] to each element arr2[]. The task is to find the count of distinct element in the array arr3[]. Examples: Input: Arr1[] = {1, 2}, Arr2[] = {3, 4}, MAX = 4 Output: 4 -&gt; 1 5 -&gt; 2 6 -&gt; 1 Explanation: Here the third array will be
15+ min read
Count all distinct pairs of repeating elements from the array for every array element
Given an array arr[] of N integers. For each element in the array, the task is to count the possible pairs (i, j), excluding the current element, such that i &lt; j and arr[i] = arr[j]. Examples: Input: arr[] = {1, 1, 2, 1, 2}Output: 2 2 3 2 3Explanation:For index 1, remaining elements after excluding current element are [1, 2, 1, 2]. So the count
7 min read
Count distinct ways to replace array elements such that product of the array becomes even
Given an array arr[] consisting of N odd integers, the task is to count the different number of ways to make the product of all array elements even, by repeatedly changing any set of elements to any values. Since the count can be very large, print it to modulo 109 + 7. Examples: Input: arr[] = {1, 3}Output: 3Explanation: All possible ways to make t
6 min read
Sum of array elements whose count of set bits are unique
Given an array arr[] consisting of N positive integers, the task is to find the sum of all array elements having a distinct count of set bits in the array. Examples: Input: arr[] = {8, 3, 7, 5, 3}Output: 15Explanation:The count of set bits in each array of elements is: arr[0] = 8 = (1000)2, has 1 set bits.arr[1] = 3 = (11)2, has 2 set bits.arr[2] =
7 min read
Partition an array into two subsets with equal count of unique elements
Given an array arr[] consisting of N integers, the task is to partition the array into two subsets such that the count of unique elements in both the subsets is the same and for each element, print 1 if that element belongs to the first subset. Otherwise, print 2. If it is not possible to do such a partition, then print "-1". Examples: Input: arr[]
13 min read
Maximize count of K unique elements that can be chosen from Array
Given an arrays arr[] of size N and an array of queries Q[] of size M, where Q[i] defines the count of unique elements that have to be chosen from the array arr[]. The task to find the maximum number of elements that can be picked for each query. Examples: Input: arr[ ] = {30, 31, 32, 33, 32, 32, 31, 30, 30, 32}, Q[ ] = {1, 3}Output: 4 9Explanation
6 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox