Track3

Question 1

Given an array containing numbers such that exactly one number occurs odd number of times and rest all occur even number of times, find the number that occurs odd times.
Eg: {2, 3, 4, 3, 5, 2, 4} A: 5

Answer 1

XOR all the numbers together and store in “result”. “result” would then contain only the number occurring odd times as (a XOR a = 0) and (a xor b) xor c = a xor (b xor c).
Time = Theta(n)

Question 2

Given ‘n’ numbers in the range 1 to (n+1) both inclusive, and each number occurring not more than once. Find the number that is missing.
Eg : {1, 3, 2, 5}
A : 4

Answer 2

result = [ (1 xor 2 xor 3 xor … xor (n+1) ) xor ( 1 xor 3 xor 2 xor 5) ]
Then ‘result’ = 4, the missing number.

Question 3

Given an array containing numbers such that exactly two numbers occur odd number of times and rest all occur even number of times, find the numbers that occur odd times.
Eg: {2, 3, 4, 3, 7, 5, 2, 4, 7, 7} A: 5,7

Answer 3

1. result = (XOR all the numbers in the array)
   now, result = (5 xor 7) = (00101 xor 00111) = 00010
2. Find the rightmost bit of “result” that is 1
   => 2nd bit from right in this case
3. Divide the array in two groups:-
   group1 = all numbers that have 2nd bit from right as 1 => 2, 3, 3, 7, 2, 7, 7
   group2 = all numbers that have 2nd bit from right as 0 = 4, 5, 4
4. number1 = (xor all numbers in group1) = 7
   number2 = (xor all numbers in group2) = 5

Question 4

Given a String like “abc”, for instance, print its power set {“”, a, b, c, ab, bc, ac, abc}

Hint : You could use bitwise operators

Answer 4

len(“abc”) = 3 , therefore size of the power set = 8 i.e. binary range from (000 to 111)

abc
000 : “”
001 : “c”
010 : “b”
011 : “bc”
100 : “a”
101 : “ac”
110 : “ab”
111 : “abc”

Question 5

Given an input int ‘n’ and another int ‘k’, write a method that returns true if the kth bit of n is set and false otherwise.

Answer 5

Use bitwise operators left shift/right shift.

1. int temp = 1; temp = temp«(k-1)
2. if((temp & n)==1)
   return true
   else
   return false

Question 6

Given a non-negative number, find the count of bits that are set.
Eg, num = 5, then 5 = (101) in binary, hence return 2.

Answer 6

count = 0
if(num>0){
num = num&(num-1)
count++;
}
if(num>0){
same as above
}
repeat until num==0

Question 7

Given a non negative number ‘n’, find whether it is a power of 2 in constant time.

Answer 7

If n is a power of 2, it will have exactly one set bit.
So we use Brian Kerningan’s algo:-

if “n &(n-1)” is 0 then n is a power of 2 else not.
Time = theta of 1