Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times.

Question

Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times. Using hash was not allowed. Complexity of algorithm should be O(n)

Answer 1

I assume the array is not sorted, or similary, repeats of a number don't appear in one contiguous run. Otherwise, the problem is really trivial: just scan the array once with a window of size 3, and if each number in that window is the same, then that's the number that repeats 3 times in one contiguous run.

If the repeats are scattered, then the problem becomes more interesting.

Since this is homework, I will only give you a hint.

This problem is a cousin of where you're given an array of unsorted integers, and all numbers appear an even number of times, except one that appears an odd number of times.

That number can be found quite easily in O(N) by performing an exclusive-or of all the numbers in the array; the result is the number that appears an odd number of times.

The reason why this works is that x xor x = 0.

So for example, 3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7.

Answer 2

Well all I can think of is this but I'm sure your prof is looking for a tricky equation that will solve this in 1 scan. You can do it in 2 scans which is O(n) assuming that you can create a 2nd array of size (0 to max number in 1st array). Scan once, find max number in array. Create 2nd array of that size. Iterate over 1st array again using 2nd array as buckets to increment a count for each element in 1st array. Once you increment a bucket to 3 that's your solution. Not the best but it would work in some cases.

Answer 3

If you know min and max of the integer sequence and min>=0, create an array [min, max] filled with zeros. Scan the given array and if i occures, increment i-th position by one. After finishing you have frequency table in the second array, where the array position points to an integer.

Answer 4

list = [1,5,2,4,7,...] // input list

// create a node data structure that looks like 
Node:
   data
   left_child
   right_child
   hit_count = 0

// create a binary tree data structure that looks like 
BinaryTree:
   node_list // add nodes at the time of building the tree

btree = BuildBinaryTree(list) // O(n)

def BuildBinaryTree(list):
    // code
    if current_node.data == current_value_form_list_you_are_trying_to_insert:
       current_node.count += 1

    if no_node_with_current_value:
       //then add node at appropriate place.

    // code

for node in btree.node_list: // O(n)
    if node.hit_count == 3:
       print node.data

I hope this works. Expecting comments (and criticism ;)

Answer 5

int count[2^32];
for x in input:
  count[x] = 0;  // delete this loop if you can assume ram is cleared to 0.
for x in input:
  count[x]++;
for x in input:
  if count[x] == 3:
    return x

Please excuse the mix of languages :-) Also, this is really stupid to have an array that can be indexed with any integer - you can do it on a 64bit system and it does meet the requirements.

Answer 6

Use radix sort (which is linear in the number of bits required to specify the integers), then scan for the triplet.

Answer 7

void main() { int a[10]={1,5,2,8,5,9,0,5,3,7},n,i,j,k=0; int p; printf("\n"); for(i=0;i<10;i++) { p=1; for(j=i+1;j<10;j++) { if(a[i]==a[j]) p++; } if(p==3) { printf("the no is: %d",a[i]); getch(); exit(0); } } printf("not available\n"); getch(); }