How can we find a repeated number in array in O(n) time and O(1) space complexity

Question

How can we find a repeated number in array in O(n) time and O(1) complexity? eg array 2,1,4,3,3,10 output is 3

EDIT: I tried in following way. i found that if no is oddly repeated then we can achieve the result by doing xor . so i thought to make the element which is odd no repeating to even no and every evenly repeating no to odd.but for that i need to find out unique element array from input array in O(n) but couldn't find the way.

Answer 1

Without knowing more about the possible values in the array you can't.

With O(1) space requirement the fastest way is to sort the array so it's going to be at least O(n*log(n)).

Answer 2

Assuming that there is an upped bound for the values of the numbers in the array (which is the case with all built-in integer types in all programming languages I 've ever used -- for example, let's say they are 32-bit integers) there is a solution that uses constant space:

1. Create an array of N elements, where N is the upper bound for the integer values in the input array and initialize all elements to 0 or false or some equivalent. I 'll call this the lookup array.
2. Loop over the input array, and use each number to index into the lookup array. If the value you find is 1 or true (etc), the current number in the input array is a duplicate.
3. Otherwise, set the corresponding value in the lookup array to 1 or true to remember that we have seen this particular input number.

Technically, this is O(n) time and O(1) space, and it does not destroy the input array. Practically, you would need things to be going your way to have such a program actually run (e.g. it's out of the question if talking about 64-bit integers in the input).

Answer 3

Use Bit manipulation ... traverse the list in one loop.

1. Check if the mask is 1 by shifting the value from i.
2. If so print out repeated value i.
3. If the value is unset, set it.

*If you only want to show one repeated values once, add another integer show and set its bits as well like in the example below.

**This is in java, I'm not sure we will reach it, but you might want to also add a check using Integer.MAX_VALUE.

    public static void repeated( int[] vals ) {
        int mask = 0;
        int show = 0;
        for( int i : vals ) {
            // get bit in mask
            if( (( mask >> i ) & 1) == 1 &&
                (( show >> i ) & 1) == 0 )
            {
                System.out.println( "\n\tfound: " + i );
                show = show | (1 << i);
            }

            // set mask if not found
            else
            {
                mask = mask | (1 << i);
                System.out.println( "new: " + i );
            }

            System.out.println( "mask: " + mask );
        }
    }

Answer 4

I met the problem too and my solution is using hashMap .The python version is the following:

  def findRepeatNumber(lists):
      hashMap = {}
      for i in xrange(len(lists)):
          if lists[i] in hashMap:
              return lists[i]
          else: 
              hashMap[lists[i]]=i+1
      return

Answer 5

It is possible only if you have a specific data. Eg all numbers are of a small range. Then you could store repeat info in the source array not affecting the whole scanning and analyzing process.

Simplified example: You know that all the numbers are smaller than 100, then you can mark repeat count for a number using extra zeroes, like put 900 instead of 9 when 9 is occurred twice.

It is easy when NumMax-NumMin

http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/

Answer 6

This is impossible without knowing any restricted rules about the input array, either that the Memory complexity would have some dependency on the input size or that the time complexity is gonna be higher.

The 2 answers above are infact the best answers for getting near what you have asked, one's trade off is Time where the second trade off is in Memory, but you cant have it run in O(n) time and O(1) complexity in SOME UNKNOWN INPUT ARRAY.

Answer 7

public static string RepeatedNumber()
    {
        int[] input = {66, 23, 34, 0, 5, 4};
        int[] indexer = {0,0,0,0,0,0}
        var found = 0;
        for (int i = 0; i < input.Length; i++)
        {
            var toFind = input[i];
            for (int j = 0; j < input.Length; j++)
            {
                if (input[j] == toFind && (indexer[j] == 1))
                {
                    found = input[j];
                }
                else if (input[j] == toFind)
                {
                    indexer[j] = 1;
                }
            }

        }


    return $"most repeated item in the array is {found}";

}

Answer 8

You can do this

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
void main ()
{
    clrscr();
    int array[5],rep=0;
    for(int i=1; i<=5; i++)
    {
        cout<<"enter elements"<<endl;
        cin>>array[i];
    }
    for(i=1; i<=5; i++)
    {
        if(array[i]==array[i+1])
        {
            rep=array[i];
        }
    }
    cout<<" repeat value is"<<rep;
    getch();
}