few problems, approaches and solutions

Category Archives: clrs

Problem 4-2

Problem:

Given, an array of size n with distinct elements such that 0 <= A[i] <= n for each element i. Note that the array should be missing an integer from range [0,n], as the array has size n and the range has n+1 elements. The only way to access elements is through function

bit_access(int * A, int i, int j)

which returns the j^{th} bit of element i in array A.

We have to find out the missing number in O(n) time.

Approach:

Let b^{th} bit be the most significant set bit of n. What we observe is that the elements of A could be divided into two sets, based on the b^{th} bit of those elements. Those which have the bit set, and those which don’t. We know that number of elements with b^{th} bit 0 should be 2^{b-1}. And the remaining elements would have the bit set. If the number of 0’s doesn’t match the expected count, then the missing element has its b^{th} bit as 0, otherwise its 1. The algorithm works on this observation by first partitioning the array according to b^{th} bit and then applying the same logic recursively on the sub-array which has the element missing from the range.

Here’s the code for partition and recursive search of solution.

/* partition array with elements, according to b bit of each
element and return the partition index. */
int partition(int * arr, int n, int b)
{
int i, part=0;

/* invar: part points to the first set bit seen so far. */
for (i=0;i optimized away.
The above recursion is T(n) = T(n/2) + O(n), which solves to O(n), hence a solution for the problem.

Advertisements

problem 2.3-7

Problem:

We are given a set S of n integers, and another integer x. And we need to find out if there exists two integers in the set S such that there sum is x.

Approach:

The straight forward answer is to calculate sum for each possible pair of elements in S, and see if any of them matches with x.

Note that the sum of the smallest element and the largest element in S, will be the median of sums possible with pairs of elements in S. If x, is less than this sum, then the largest element of S could not be in the pair we are searching for. Similarly, if x is larger than the required sum, then the smallest element from S will not be in the pair we are searching for. The same method could be applied to the subproblem(the remaining list).

At each stage we have to calculate the smallest and largest element in the list. We could solve this for each subproblem in O(n), or we could sort the set S initially, and then access the smallest and largest elements in O(1). The second approach solves the problem in O( n log n).

Coding the approach:

As u might have noticed, the solution is a recursive one. But it doesn’t have to be coded that way. The recursive solution could be easily converted to an iterative one, as shown below. I have skipped the much of the code, just to present heart of the method.

int sum_check(int *arr, int n, int x)
{
  int u, l, s;
  u=0;l=n-1;

  while (u<l) {
    s = arr&#91;u&#93;+arr&#91;l&#93;;
    if (x < s)
      l--;
    else if (x > s)
      u++;
    else
      return 1;
  }

 return 0;
}

But lets see the recursive approach also.

int sum_check_rec(int *arr, int n, int x)
{
int s = arr[0] + arr[n-1];

if (n == 1) return 0;
if (x == s) return 1;

return sum_check_rec(arr + (x