Find one number on the list when other numbers are more than doubled

Question

The problem expands from the search for a singular in the list

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

Does anyone have a 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) and the complexity of the space O (1)?

Answer 1

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

This method will not work if at least the element has more than n. In this case, you should use the method suggested by Jayram

EDIT:
To get an array, just apply mod n to each element of the array

Answer 2

This can be solved in the set with your restrictions, if numbers other than lonely number occur exactly in an even number (i.e. 2, 4, 6, 8 ...), performing the XOR operation for all numbers, But except in cosmic complexity O(1) it just teases me.

If you do not use these restrictions, you can use these approaches to solve this problem.

• Sort numbers and current variable to get the current number score. If it is greater than 1, go to the next number and so on. Space O (1) ... Time O (nlogn)
• Use O (n) extra memory to count the occurrences of each number. Time O (n) ... Space O (n)

Answer 3

According to banarun solution (with a little fix):

Algorithm Conditions :

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

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 associated with the time complexity O (N) and the spatial complexity O (1)

Note: Again this algorithm can only work if all numbers are positive and all numbers are less than N.

Answer 4

I just want to extend @banarun's answer.

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

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

There is no iteration over the map and for each i myMap add P to myMap(myMap(i)%P) , if myMap(myMap(i)%P) not triggered, set it to P Now iterate again through myMap , the position at which myMap[i] is >=P AND < 2*P is your answer. Basically, the idea is to remove the overflow problem and overwrite from the banaruna proposed by Algo.

Answer 5

Here is a mechanism that may not be as good as others, but that is instructive and comes to the bottom of why the XOR answer is as good as 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 an array

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

The view in mod 3 has the form

 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 

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

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

Why is the XOR answer in O(n) ? Because the processor provides an XOR operation that runs in O(1) time, not the O(r) factor that we have above.