few problems, approaches and solutions

Monthly Archives: May 2008

subtleties of programming

While coding for the problem-2.3-7 , some how I was not in my default mode of not thinking while coding. To test my programs I was writing a random array generator. One part of it was to swap two array entries. Now, the most straight forward way to swap two array elements is

int tmp = arr[i];
arr[i]  = arr[r];
arr[r]  = tmp;

But, knowing the xor method, I thought why not save a variable. Basically, if a and b are to be swapped, then the code suffices.

a ^= b;
b ^= a;
a ^= b;

So now the question is, would this work on an array. Ex.

arr[i] ^= arr[r];
arr[r] ^= arr[i];
arr[i] ^= arr[r];

Here’s a subtle bug. If i and r are same, then it wont. The reason being that we loose the original value. If both indexes are same, the same array entry would be xor’ed with itself. Wiki page explains it better, and why it should be avoided in desktop systems. Again, I learn the evils of premature optimization. Subtleties of programming!

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