Find the count of distinct elements in an array

Find the count of distinct elements in an array

1

123

2

413

2

5

1

2

4

Result: 6

This is an interesting problem and has got different solutions. The factors to consider are:

1) Size of the input
2) Range of input e.g. 1 to 100
3) Can we use additional resources i.e. memory or not

There are different ways we can solve this problem:

Solutions 1:

The first solution iterates through the elements and checks if the element is already counted as distinct element. This solution does not consider the input range or size and is computationally expensive.

//Array 

int[] values = { 1, 2, 3, 4, 2, 1, 5, 7 };

//set the distinct count as 0

var distinctCount = 0;

//iterate through all the elements

for (int i = 0; i < values.Length; i++)

{

 //Take it as the it is a new element and increase the distinct count

 distinctCount++;

 var alreadyCounted = false;

 //check if the element is already counted

 for (int j = 0; j < i && !alreadyCounted; j++)

  if (values[i] == values[j]) //if already counted

  {

   distinctCount--; // decrease the distinct count

   alreadyCounted = true; // exit the inner loop

  }

}


return distinctCount;

Complexity of this solution is: O()

Solutions 2:

This solution also does not consider the size or the range of the input. But it sorts the array before checking the distinct count.

// declaring and initialising the array 

int[] values = { 1, 2, 3, 4, 2, 1, 5, 6 };

//set the distinct count as 0

int distinctCount = 0;

//Sort the array

Array.Sort(values);

int lastValue = 0;

for (int i = 0; i < values.Length; i++)

{

 if (i == 0 || values[i] != lastValue) // either it is the first element or not the same as previous element

  distinctCount++; //add to the distinct count

 lastValue = values[i];

}

// Console.WriteLine($"Total number of distinct elements are: {distinctCount}");

return distinctCount;

The complexity of this solution mainly depends sorting algorithm used say merge sort then O(n log(n)).

Solutions 3:

This solution uses the fact that we have got limited input e.g. input is between 1 to 100. It uses additional resources. An array in this case representing the input.

//declaring and initialising the array 

int[] values = { 1, 2, 3, 4, 2, 1, 5, 99 };

//declare another array defining the range of input

int[] numberCount = new int[100];

//set the distinct count as 0

int distinctCount = 0;

for (int i = 0; i < values.Length; i++)

{

 numberCount[values[i]]++; //increase the number count

 if (numberCount[values[i]] == 1) //if this is the first occurence of number

  distinctCount++;

}

//Console.WriteLine($"Total number of distinct elements are: {distinctCount}");

return distinctCount;




 

The complexity of this solution in O(n).

Solutions 4:

This solution uses additional resources and the range of values is not defined. 

int[] values = { 1, 2, 3, 4, 2, 1, 5, 99 };

Hashtable elements = new Hashtable();

for (int i = 0; i < values.Length; i++)

{

 if (!elements.Contains(values[i]))

  elements.Add(values[i], 1);

}

Console.WriteLine($"Total number of distinct elements are: {elements.Count}");

The complexity of this solution is O(n).


There are different ways to solve this problem. I have listed a few. Please feel free to comment or add to the list solutions.