Problem 6 (15 Points) Divide and conquer An array a[1..n] contains all numbers from 0 to n with one exception. The goal is to determine the missing number in O(n) time. The only way to access the array a is by an operation "fetch the i th bit of a[j] ", which takes contant time. (a) How many least signficant bits are equal to 0 in the numbers from 0 to n ? (b) How many least signficant bits are equal to 1 in the numbers from 0 to n ? (c) How can you determine the least signficant bit of the missing number? (d) How many numbers in 0..n have the same least significant bit as the missing number. If LSB (missing number) =0, then If LSB (missing number) =1, then (e) (i) Sketch the main idea of the O(n) divide-and-conquer algorithm that was given in the sample solution of the homework. (ii) What subproblem will be solved in subsequent iterations? (iii) What is the size of the subproblem? (iv) Why has the algorithm O(n) time complexity