CODEWITHSUNDEEP
arraysalgorithmnumbers
JAN
JAN

Reputation: 21885

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

Given an array that has the numbers {0......2^k -1} except for one number , find a good algorithm that finds the missing number.

Please notice , you can only use :

My answer : use divide & conquer , check the bit number K of all the numbers , if the K bit (now we're on the LSB) is 0 then move the number to the left side, if the K bit is 1 then move the number to the right side. After the 1st iteration , we'd have two groups , where one of them is bigger than the other , so we continue to do the same thing, with the smaller group , and I think that I need to check the K-1 bit this time.

But from some reason I've tried with 8 numbers , from 0.....7 , and removed 4 (say that I want to find out that 4 is the missing number) , however to algorithm didn't work out so good. So where is my mistake ?

Upvotes: 5

Views: 974

Answers (5)

fatima
fatima

Reputation: 11

you can consider elements as string of k bits and at each step i if the number of ones or zeros in position i is 2^(k-i) you should remove all those strings an continue for example 100 111 010 101 110 000 011 so 100 111 101 110 all will be removed and between 010 000 011 , 010 and 011 will be removed because their second bit is 1 000 remain and its rightmost bit is zero so 001 is the missing number

Upvotes: 1

UmNyobe
UmNyobe

Reputation: 22910

Given the fact that for a given bit position j, there are exactly 2^(k-1) numbers which have it set to 0, and 2^(k-1) which have it set to 1 use the following algorithm.

 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

If a position is false at the end then the missing number does have a zero at this position, otherwise it has a one (for k >1, If k = 1 then it is the inverse). Now to implement your array of booleans create a number of size 2k, where the lower k are set to 0, and the upper are set to 1. Then

invert the boolean at position j

is simply *

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

With this representation the missing number is the lower k elements of the array B. Well this algorithm is still O(k*2^k) but you can say it is O(n*log(n)) of the input.

Upvotes: 1

user1196549
user1196549

Reputation:

Ron,

your solution is correct. This problem smells Quicksort, doesn't it ?

What you do with the Kth bit (all 0's to the left, 1's to the right) is a called a partition - you need to find the misplaced elements in pairs and swap them. It's the process used in Hoare's Selection and in Quicksort, with special element classification - no need to use a pivot element.

You forgot to tell in the problem statement how many elements there are in the array (2^k-2 or more), i.e. if repetitions are allowed.

If repetitions are not allowed, every partition will indeed be imbalanced by one element. The algorithm to use is an instance of Hoare's Selection (only partition the smallest halve). At every partition stage, the number of elements to be considered is halved, hence O(N) running time. This is optimal since every element needs to be known before the solution can be found.

[If repetitions are allowed, use modified Quicksort (recursively partition both halves) until you arrive at an empty half. The running time is probably O(N Lg(N)) then, but this needs to be checked.]

You say that the algorithm failed on your test case: you probably mis-implemented some detail.

An example:

Start with 5132670 (this is range {0..7})

After partitioning on bit weight=4 you get 0132|675

where the shortest half is 675 (this is range {4..7})

After partitioning on bit weight=2, you get 5|67

where the shortest half is 5 (this is range {4..5})

After partitioning on bit weight=1, you get |5

where the shortest half is empty (this is range {4}). Done.

Upvotes: 3

kilotaras
kilotaras

Reputation: 1419

I assume you can build xor bit function using get bit j.

The answer will be (xor of all numbers)

PROOF: a xor (2^k-1-a) = 2^k-1 (a and (2^k-1-a) will have different bits in first k positions).
Then 0 xor 1 xor ... xor 2^k-1 = (0 xor 2^k-1) xor (1 xor 2^k-2).... (2^(k-1) pairs) = 0.
if number n is missing the result will be n, because 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: This will not work if k = 1.

Upvotes: 5

shift66
shift66

Reputation: 11958

for n just add them all and subtract the result from n*(n+1)/2
n*(n+1)/2 is sum of 1...n all numbers. If one of them is missing, then sum of those n-1 numbers will be n*(n+1)/2-missingNumber
Your answer is: n*(n+1)/2-missingNumber where n is 2^k-1

Upvotes: 3

Related Questions