Given an array of integers where some numbers repeat 1 time or 2 times but one number repeats 3 times, how do you find it?

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

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

Answer 3

Here's an answer that assumes max(A) is reasonably small, where A is the input array:

int ValidCount(int[] a, int[] b, int i, int n) {
  int num = a[i];
  int ret = 0;
  if (b[3*num] >= 0 && b[3*num] < n && a[b[3*num]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+1] < n && a[b[3*num+1]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+2] < n && a[b[3*num+2]] == num) ret++;
  b[3*num+ret] = i;
  return ++ret;
}

int threerep(int[] A, int aSize) {
  int *B = malloc(sizeof(int) * 3 * max(A, aSize)); /* Problematic if max(A) is large */
  /* Note that we don't rely on B being initialized before use */
  for(int i = 0; i < aSize; i++) {
    if (ValidCount(A, B, i, aSize) == 3) return A[i];
  }
  return ERROR_NO_ANSWER;
}

Answer 4

Essentially, the problem is to compute the mode of the array. This solution works "ONLY" if the array range is [0,n-1]. Putting the solution here since the problem does not put a clause of the range.

• Assume that 'n' is the size of the array
• Scan the array and mark A[A[i]]=A[A[i]]+n -----> 1st pass
• Divide each array element by 'n', i.e A[i]=A[i]/n ----> 2nd pass
• The element with the maximum value from the 2nd pass is the answer.

This is O(n) with O(1) space (but with a range clause).

I am not aware of any algorithm to compute the mode in O(n),O(1) with no clauses on the range.

Answer 5

i dont see what all the fuss is about: using python 2.6 and a simple function which goes over the list, counts occurances, once it finds a number that occurs 3 times, returns it.

>>> def find3(l):
    from collections import defaultdict
    d = defaultdict(int)
    for n in l:
        d[n]+=1
        if d[n] == 3:
            return n


>>> print find3([1,1,1,2,3,4,5,6,7])
1
>>> print find3([1,1,2,3,4,5,6,7,5])
None
>>> print find3([1,1,2,3,4,5,6,7,5,4,5,5])
5

Answer 6

Bugaoo's algorithm looks neat that is quoted below. Actually, we can generalize it by doing an extra pass before "1st pass" to find min(A) and max(A) and another extra pass to move each element in A to the range of min(A) and max(A), i.e., A[0]-min(A). After "1st pass" and "2nd pass" (note that we should mod the elements by max(A)-min(A) instead of n), we could add min(A) to the duplicated number found at last.

Essentially, the problem is to compute the mode of the array. This solution works "ONLY" if the array range is [0,n-1]. Putting the solution here since the problem does not put a clause of the range. Assume that 'n' is the size of the arrayScan the array and mark A[A[i]]=A[A[i]]+n -----> 1st pass Divide each array element by 'n', i.e A[i]=A[i]/n ----> 2nd pass The element with the maximum value from the 2nd pass is the answer. This is O(n) with O(1) space (but with a range clause). I am not aware of any algorithm to compute the mode in O(n),O(1) with no clauses on the range.

Answer 7

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 8

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 9

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 10

This Algorithm looks pretty good one.... but i don't know its implementation.. Only pseudocode.... If any1 good try his hands on code(C programming), then please post it....

PseudoCode goes here... Take two bitset arrays of size n. We can use this array to count upto three occurrences i.e. if array1[i] = 1 and array2[i] = 1, then it means we have three occurrences of i+1th element.

for each integer 'i' if(array2[i] == 1) array2[i] = 0, array1[i] = 1; else array2[i] = 1;

for each element K in the arrays if (array1[k] && array2[k]) return k;

Complexity = O(n) and Space = 2n bits.

Answer 11

I'll present a solution that works in general general, such that one number occurs m times and others n times.

We need an operator that cancels out n occurrences of a integer but keeps m occurrences. If we convert each number to its binary representation, and for each bit position, count the number of times that this bit is set, the value will be a multiple of n for all numbers that occur n times, plus 0 or m for the corresponding bit of the lone integer.

If we then take modulo n of each of these counts, and divide by m, the result is the value of the corresponding bit position for the lone integer. All that's left is to convert the binary result to decimal formal.

For example, given array = [3, -4, 3, 3], m = 1 and n = 3:
Binary of 3 = 011
Binary of -4 (2s complement) = 11111111111111111111111111111100

Bit 0: 3 % 3 = 0
Bit 1: 3 % 3 = 0
Bit 2 through 32: 1 % 3 = 1
The result is -4