6

The problem is extended from Finding a single number in a list

If I extend the problem to this: What would be the best algorithm for finding a number that occurs only once in a list which has all other numbers occurring exactly k times?

Does anyone have good answer?

for example, A = { 1, 2, 3, 4, 2, 3, 1, 2, 1, 3 }, in this case, k = 3. How can I get the single number "4" in O(n) time and the space complexity is O(1)?

Community
  • 1
  • 1
Boris
  • 109
  • 6
  • So basically, aside from the space for the array itself, we only get enough room to store one number? How big can this number be, 32-bit, 64-bit, what? (I assume not arbitrarily large) – Dennis Meng Oct 30 '13 at 05:37
  • Or do we not even get that, and have to do all of our work in the space for the array (and thus have to do some weird foo in-place)? – Dennis Meng Oct 30 '13 at 05:41
  • Sorry for the ambiguity, "without extra memory" just means the space complexity is O(1). All the numbers are 32-bit integers. You can declare some integers to store some temporary values. – Boris Oct 30 '13 at 05:43
  • @DennisMeng I think he means O(1) memory else this problem wouldn't make sense. O(1) memory means that you can use extra memory so long as that memory doesn't scale proportionally with the size of your array/list. i.e. the memory used is of a constant amount regardless of input size and the constant < n. – Shashank Oct 30 '13 at 05:44
  • Yes, as Shashank said, the memory shouldn't scale proportionally with the size of your array/list. Thanks. – Boris Oct 30 '13 at 05:49
  • One step is that you add all the numbers, check whether the sum is 3N, 3N-1 or 3N+1. The number should also be of same type. This way you can reduce the size of array to n/3. But still how to proceed further? – Abhishek Bansal Oct 30 '13 at 05:50
  • If there are no restrictions on the numbers (e.g. all consecutive natural, etc), I daresay this problem is impossible to solve with the constraints you give. – Shashank Oct 30 '13 at 05:53
  • @AbhishekBansal No, that won't help. You could get an input where all of the integers are the same mod 3, in which case your added step actually does nothing at all. – Dennis Meng Oct 30 '13 at 05:54
  • @ShashankGupta Well, we can just reuse the old strategy for even `k`. But I agree, there might not be a solution for odd `k`. – Dennis Meng Oct 30 '13 at 05:56
  • Yeah even k is trivial with XOR. – Shashank Oct 30 '13 at 05:58
  • 1
    are the numbers guaranteed to be from 1 to (n/k)+1 – banarun Oct 30 '13 at 06:03
  • No, could be any unsigned int. – Boris Oct 30 '13 at 06:24

5 Answers5

4

If every element in the array is less n and greater than 0.
Let the array be a, traverse the array for each a[i] add n to a[(a[i])%(n)].
Now traverse the array again, the position at which a[i] is less than 2*n and greater than n (assuming 1 based index) is the answer.

This method won't work if at least on element is greater than n. In that case you have to use method suggested by Jayram

EDIT:
To retrieve the array just apply mod n to every element in the array

banarun
  • 2,305
  • 2
  • 23
  • 40
  • 3
    That's... actually really slick. (Also, you could probably do one pass to find the maximum, and use the maximum instead of `n`, though I suppose you might run into overflow issues.) – Dennis Meng Oct 30 '13 at 06:32
  • I'm pretty sure this doesn't work...Also isn't there the danger of overwriting the number? – Shashank Oct 30 '13 at 06:40
  • 1
    @ShashankGupta Even if you overwrite the number, the idea is that the remainder mod n is always the same, so if n is big enough, you can use mod to recover the old number. – Dennis Meng Oct 30 '13 at 06:42
  • But now that I think about it, my suggestion with the maximum doesn't help. Darn. – Dennis Meng Oct 30 '13 at 06:44
  • Yeah alright, I get that you can recover the old number with mod...But I tried implementing it in Python and it didn't work. Question, for the example array, is n = 5 (since all numbers < 5) or n = 10 (length of array)? I tried both ways and couldn't get it to work. :\ – Shashank Oct 30 '13 at 06:47
  • 1
    I mean if you look at the algorithm...think about what it will do for the example array [1, 2, 3, 4, 2, 3, 1, 2, 1, 3]. All values are 1,2,3,4 right? So if n = 10 this will modify the array to [1, 32, 33, 34, 12, 3, 1, 2, 1, 3]. Only indexes 1 through 4 will be touched. And there will be several values > 3*n and several values < 3*n. Or am I thinking of this wrong? – Shashank Oct 30 '13 at 06:52
  • For n = 5, the array would be [1, 17, 18, 19, 7, 3, 1, 2, 1, 3]. Still we have several positions where a[i] < 3*n and several positions where a[i] > 3*n. I don't get how this would work. – Shashank Oct 30 '13 at 06:53
  • You pointed it right @ShashankGupta I don't know why banarun is not responding? – Jayram Oct 30 '13 at 06:55
  • I mean I guess the detail is that you only look at the indexes 1-4. And then you realize that only one of those values will be less than 3*n (a[4]). So maybe the second iteration just needs to be described better. You only look at the indexes for which the value was an original value in the array. – Shashank Oct 30 '13 at 06:56
  • I think @One Man Crew have a good fix/solution for this answer!!! see One Man Crew answer –  Oct 30 '13 at 08:55
  • I have made edit to my answer, please point out if something is wrong – banarun Oct 30 '13 at 09:10
2

This can be solved in given with your constraints if the numbers other than lonely number are occurring exactly in even count (i.e. 2, 4, 6, 8...) by doing the XOR operation on all the numbers. But other than this in space complexity O(1) its just teasing me.

If other than your given constraints you could use these approaches to solve this.

  1. Sort the numbers and have a current variable to get the count of current number. If it is greater than 1 then go to next number and so on. Space O(1)...Time O(nlogn)
  2. Use O(n) extra memory to count the occurrences of each number. Time O(n)...Space O(n)
Jayram
  • 18,820
  • 6
  • 51
  • 68
  • 1
    could you please add a comment for voting down? What is wrong? – Jayram Oct 30 '13 at 06:24
  • My guess is that it's because the other answer shows that O(1) space is a lot more possible than you let on, but I'm not the downvoter, so I can't be sure. – Dennis Meng Oct 30 '13 at 06:38
  • that's fine. Its good that you pointed. Yeah I also up-voted that answer. But the down vote was before that answer was posted. @DennisMeng – Jayram Oct 30 '13 at 06:40
  • If you use radix-sort, then attempt #1 is of time complexity O(n). However, Space complexity is O(n*n) afaik. – alzaimar Oct 30 '13 at 07:14
  • Which one you are talking about? @alzaimar – Jayram Oct 30 '13 at 07:17
  • 1
    @alzaimar Radix sort isn't O(n) time / O(n^2) space, it's O(kn) / O(n + k), where k is the maximum number of digits of a number. – Bernhard Barker Oct 30 '13 at 08:26
  • I thought if you consider k to be 32 (bits) constant, hence O(n) in this case. – alzaimar Oct 30 '13 at 16:16
0

I Just want to extend @banarun answer .

Take the input as map . Like a[0]=1; Then take it as myMap with 0 as index and 1 as value .

And while reading the input find the maximum number M . Then find A prime greater than M as P.

No iterate through the map and for every key i of myMap add P to myMap(myMap(i)%P) if myMap(myMap(i)%P) is not initiated set it to P. Now iterate through the myMap again, the position at which myMap[i] is >=P And < 2*P is your answer. Basically the the Idea is to remove overflow and overwrite problem from the banarun suggested Algo .

MissingNumber
  • 1,142
  • 15
  • 29
0

According to banarun solution(with small fix's):

Algorithm conditions:

 for each i arr[i]<N (size of array)
 for each i arr[i]>=0 (positive)

The Algorithm:

int[] arr = { 1, 2, 3, 4, 2, 3, 1, 2, 1, 3 };
for (int i = 0; i < arr.Length; i++)
{
    arr[(arr[i])%(arr.Length)] += arr.Length;
    if(arr[i] < arr.Length)
        arr[i] = -1;
}
for (int i = 0; i < arr.Length; i++)
{

     if (arr[i] - 3 * arr.Length <0 && arr[i]!=-1)
          Console.WriteLine("single number = "+i);
}

This solution is with Time complexity of O(N) And Space complexity of O(1)

Note: Again this algorithm can work only if all number are positives and all numbers are less then N.

Community
  • 1
  • 1
One Man Crew
  • 9,420
  • 2
  • 42
  • 51
0

Here is an mechanism which may not be as good as the others but which is instructive and gets to the core of why the XOR answer is as good as it is when k = 2.

1. Represent each number in base k. Support there are at most r digits in the representation
2. Add each of the numbers in the right-most ('r'th) digit mod k, then 'r - 1'st digit (mod k) and so on
3. The final representation of r digits that you have is the answer.

For example, if the array is 

A = {1, 2, 3, 4, 2, 3, 1, 2, 1, 3, 5, 4, 4}

Representation in mod 3 is 

A = {01, 02, 10, 11, 02, 10, 01, 02, 01, 10, 12, 11, 11}

r = 2
Sum of 'r'th place = 2
Sum of the 'r-1'th place = 1

Hence answer = {12} in base 3 which is 5.

This is an answer which will be O(n * r). Note that r is proportional to log n.

Why is the XOR answer in O(n) ? Because the processor provides an XOR operation which is performed in O(1) time rather than the O(r) factor that we have above.

user1952500
  • 6,611
  • 3
  • 24
  • 37