Geek Answers Handbook

Find the missing number in the group {0 ...... 2 ^ k -1}

For an array with numbers {0......2^k -1}except one number, find a good algorithm that will find the missing number.

Please note that you can only use:

  • to A[i]return a bit value j.

  • replace A [i] with A [j].

My answer: use divide and conquer, check the K bit of all numbers if the bit is K (now we are on LSB) 0, then move the number to left side, if the Kbit 1, then move the number to right side. After the 1st iteration, we will have two groups, where one of them is larger than the other, so we continue to do the same with a small group, and I think I need to check bit K-1 time.

But for some reason I tried with 8 numbers, from 0.....7and deleted 4(let's say I want to know what 4is the missing number), however, the algorithm did not work so well. So where is my mistake?

+5
source share
5 answers

Ron

Your decision is correct. This problem smells like Quicksort, right?

What you do with the Kth bit (all 0 to the left, 1 to the right) is called a section - you need to find non-local elements in pairs and change them. This is the process used in Hoare Selection and Quicksort, with a special classification of elements - there is no need to use a rotation element.

You forgot to indicate in the problem description how many elements are in the array (2 ^ k-2 or more), i.e. if repetition is allowed.

, . Hoare Selection ( ). , , , O (N). , , .

[ , Quicksort ( ), . , , O (N Lg (N)), .]

, : , , .

:

5132670 ( {0..7})

= 4 0132 | 675

675 ( {4..7})

= 2, 5 | 67

5 ( {4..5})

= 1 | 5

( {4}). .

+3

, xor bit, get j.

(xor )

: a xor (2^k-1-a) = 2^k-1 (a (2 ^ k-1-a) k ).
0 xor 1 xor ... xor 2^k-1 = (0 xor 2^k-1) xor (1 xor 2^k-2).... (2^(k-1) pairs) = 0.
n , n, 0 xor 1 xor 2....xor n-1 xor n+1 xor ... = 0 xor 1 xor 2....xor n-1 xor n+1 xor ... xor n xor n = 0 xor n = n

EDIT: , k = 1.

+5

n n * (n + 1)/2
n * (n + 1)/2 1... n . , n-1 n * (n + 1)/2- missingNumber
: n * (n + 1)/2- missingNumber, n 2 ^ k-1

+3

, j 2^(k-1) , 0, 2^(k-1), 1, .

 start with an array B of boolean of size k 
 init the array to false everywhere
 for each number A[i]
   for each position j 
    get the value v
    if v is 1 invert the boolean at position j
   end for
 end for

, , ( k >1, If k = 1, ). 2k, k 0, 1.

invert the boolean at position j

*

 swap B[j] with B[j+k].

- k B. , O(k*2^k), , O(n*log(n)) .

+1

you can consider the elements as a string of k bits and at each step i, if the number of ones or zeros in position i is 2 ^ (ki), you must delete all these lines, for example, continue 100 111 010 101 110 000 011 so 100 111 101 110 all will be deleted and between 010 000 011, 010 and 011 will be deleted because their second bit is equal to 1,000 remain and its rightmost bit is zero, therefore 001 is the missing number

+1
source

More articles:


All Articles