A is an arrays: determine if there are two integers that are present in A the same number of times

Question

For example: A=[1,2,2,3,4,4,5]->true; A=[1,2,2,3,3,3,4,4,4,4]->false.

proc(A){
list = newList()
for (i=1 to length[A]) {
   occ = 0
   n = a[i]
   for (j = 1 to length[A]) {
       if(a[j] == n)
            occ++
    } 
    list.append(occ)
}

but dosen't work because in the list will be repeated elements.I thought about using an algorithm similar to countingSort but I don't know the length of the support vector.

Any help? In pseudocode will be fine. Thank you.

Answer 1

With the use of data structures like map and set, this task could be accomplished very easily.

Algorithm:-
-> Loop through the array and store it in hashmap with key as the value of the array element and value as the count of it's occurrence.
-> Create an empty set
-> Loop through the map and keep storing the value of every key in the set and if somewhere in between looping u come across any value that's already there in the set, then return true else if u reach the end of map, then return false.

Let's look as Pseudocode now.

Pseudocode:-
-> we have input array as arr and length n
-> we create an empty map - m[int, int]
-> for (i -> 0 to n-1)
   {
      m[arr[i]]++;
   }
-> This in the end will give us our map which we want with key as the array element and value as it's count
-> create a set - s
-> iterate over map m as key -> value
   {
      if (value present in s) {
         return true
      }
      s.insert(value)
    }
-> If we reach here then it means we never came across any pair of elements whose occurrence is same, so return false.

Hope this helps!