3 sum problem

The problem is defined as given a array find a set of elements such that c=a+b.

Approach
1. Sort the array
2. for each element c=arr[i] in the array
3. left=0; right=i;
4. while left<right
5. check if c==arr[left]+arr[right]
6. then add c to output
7. else if c<arr[left]+arr[right] right--
8. else left++
9. end
10.end

#include <iostream>

using namespace std;

int compare (const void * a, const void * b);
void sum3(int arr[], int n);
void main(){
 int arr[]={2,3,5,1,4,9};
 
 qsort(arr,6,sizeof(int),compare);

 sum3(arr,6);

}
void sum3(int arr[], int n){
 int l,r;
 int count=0; 
 int index[6];
 int curr=0;
 for(int i=n-1;i>=0;i--)
 { 
  l=0; r=i;
  while(l<r){
   curr=arr[l] +arr[r];  
   if(arr[i] == curr){
    index[count++]=i; 
    cout<<arr[i]<<" ";
    break;
   }
   else if(arr[i] < curr)
    r--;
   else l++;
  }
 }
}
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

Complexity of the above procedure is O(n^2). Apparently a better solution for the problem doesn't exist. Also, a number of problems can be reduced to the 3 sum problem and are called 3sum hard.

Implement a queue using 2 stacks

Use 2 stacks, S and T

1. Enqueue
S.push()

2. Dequeue
if T.count==0
while (S.count>0) t.push(s.pop());

T.pop();

The operations take O(1) amortized time.

Reference
C SC 545 Exam Fall 08

Kth smallest in merge of 2 sorted arrays

Idea:
The solution goes like this

A[1...m] B[1...n]

1. Compare A(k/2) and B(k/2)
if A(k/2) < B(k/2)

So the kth smallest can't be in A[1..k/2] and B[k/2+1 .. n]. A[1...k/2] < Kth smallest < B[k/2+1 ... n]

So we discard these elements. And now search for the k/2th smallest number in the 2 remaining arrays

if the reverse is true we do the same operation but with B and A swapped

2. if m<k

we discard B[1...k-m-1]

and look for (m+1)th (= k-(k-m-1)) smallest element in remaining arrays

const trick

1. const int* x=5;

Declares a pointer to a constant.
So now a assignment *x=10; will fail

2. int* const x=5;
Declares a constant pointer to a variable.
so *x=10 will PASS while x=10 will fail.

3. const int * == int const *
The above 2 mean the same thing

4. const int const *x=5;

Using 3. statement 4 Declares a pointer to a constant. (same as 1)

New vs. Malloc

New calls the "operator new(...)" method to allocate memory (like what malloc does), but memory allocation is followed by a call to the appropriate constructor. Also new is type-safe, yet malloc is not.

Static function in C

A static function is a function with the static qualifier applied:

static void foo ( void )
{
/* Blah blah */
}
What it does is restrict visibility of the function to the translation unit in which it's declared. Functions are implicitly declared as extern by default, which means they're visible across translation units.

Reference
http://www.daniweb.com/forums/thread82504.html

Maximum Sum Sub array

This is a interesting problem which can be solved in a variety of ways. This problem has a chunk of a chapter devoted in the Programming Pearls book by Jon Bentley.

Method 1. Brute Force O(n^2)

This involves taking each index i between 0 to len and for every other index j>i calculate the sum while keeping track of the maximum.

private static int sumbruteforce(int [] arr){
  int sum=0;
  int max=Integer.MIN_VALUE;
  int maxi=0;
  int maxj=0;
  for(int i=0;i<arr.length;i++){
   sum=0;
   for(int j=i;j<arr.length;j++){
    sum+=arr[j];
    if(sum>max){
     max=sum;
     maxi=i;
     maxj=j;
    }
   }  
  }
  System.out.println(maxi+" "+maxj);
  return max;
 }

2. Method 2: Divide and Conquer: O(n log n)
This involves dividing the array recursively into 3 parts left, right and mid. And comparing max sum of the three.

Calculating max(left) and max(right) is trivial using recursion. For the mid element, we know the left bound (l) lies in left half and right bound (r) lies in right half. So we calculate l s.t sum of elements between l and mid is max and r s.t the sum is maximum for elements between mid and right.

private static int sumDivConquer(int [] arr, int l, int h){
  if(l>h)
   return 0;
  if(l==h)
   return arr[l];

  
  int m=(int) Math.floor((double)((l+h)/2));
  int max=0;
  
  max=sumDivConquer(arr, l, m);
  max=Math.max(max,sumDivConquer(arr, m+1, h));
  
  
  int L=0;
  int R=0;
  int S=0;
  for(int i=m;i>=l;i--){
   S+=arr[i];
   L=S>L? S:L;
  }
  R=S=0;
  for(int i=m+1;i<=h;i++){
   S+=arr[i];
   R=S>R? S:R;
  }
  max=Math.max(max, L+R);
  
  return max;     
 }

3. Dynamic programming O(n)

An optimized DP solution takes O(n).

The naive DP solution acts exactly like method 1 and generates a matrix A[i,j] containing sum of elements with left bound i and right bound j.

The optimized DP constructs a single dimension table of array size, with
table[i]: Represents the sum of subarray with maximum sum terminating at i;

for i=0, table[0]=arr[0]
for i>0, table[i]= Max{ arr[i], arr[i]+table[i-1]}

Once we have the table finding max sum takes only a single pass through the above table, we can fasten the procedure up by keeping track of max side by side.

private static int sumDP(int [] arr){
 int table[]=new int[arr.length];
 table[0]=arr[0];
 for(int i=1;i<arr.length;i++){
  table[i]=Math.max(arr[i], arr[i]+table[i-1]);
 }
 int max=Integer.MIN_VALUE;
 for(int i=0;i<arr.length;i++){
  if(table[i]>max)
   max=table[i];
 }
 return max;
}
 

A simpler algorithm based on the same idea as the DP method is called Kadane's algorithm and it works without the need of maintaining the auxiliary table.

The code is derived from here

private static int sumKadane(int arr[]){
    int max=Integer.MIN_VALUE;
    int a,b; a=b=0;
    int curr = 0;
    int aa = 1;
    for (int bb= 1;bb<arr.length;bb++){
        curr = curr + arr[bb];
        if (curr > max) {
            max=curr;
            a=aa;
            b=bb;             
        }
        
        if (curr < 0) {
            curr = 0;
            aa = bb + 1;
        }
    }
    System.out.println(a+" "+b);
    return max;
}

Counting Number of set bits in a number

1. Method 1

Complexity= O(n)

int numOfOnes(int n){
  int count=0;
  while(n!=0){
   if((n & 1) == 1)
    count++;
   n=n>>>1;
  }
  return count;   
 }

Method 2:
The method works as follows:

The operation:
n=n&(n-1)
resets the last set bit of n.

So the number of time the above operation can be done before n is equal to 0 are the number of set bits in n originally.

Complexity= O(m) where m is the number of set bits in n.

int numOfOnes2(int n){
 int count=0;
 while(n!=0){
  n=n&(n-1);   
  count++;
 }
 return count;
}

Also note that if count above is 1, then number n is a power of 2.

Generating Combinations

The algorithm for this is very similar to the algorithm for generating permutations.

Algorithm:
1. Remove Item i from elements and put in output array
2. Display Output
3. Generate combinations for rest of the array

public void combine(String str){
  int l=str.length();  
  StringBuilder out=new StringBuilder();
  char []in=str.toCharArray();
  doCombine(in,out,l,0);
 }
 private void doCombine(char[] in, StringBuilder out, int n, int start){
  for(int i=start;i<n;i++){   
   out.append(in[i]);
   System.out.println(out);
   if(i<n)
    doCombine(in, out, n, i+1);
   
   out.setLength(out.length()-1);
  }
 }

Generating Permutations

This has been a problem I always had difficulty with. The only resort I had till now was to memorize the solution and spit it out when needed. But now, with a algorithms class behind me and a little bit more insight into the problem, I can atlast cook up the logic here.

SO, the Question is:
Given n items (numbers, chars) generate/print all possible permutation of them

Algorithm:
1. Take a item i and put it in the perm array
2. Generate Permutation for rest of the n-1 elements (Print perm array when n==0)
3. Put back Item i in elements

public class Permute {
 public void permute(String str){
  int l=str.length();
  boolean [] used=new boolean[l];
  StringBuilder out=new StringBuilder();
  char []in=str.toCharArray();
  doPermute(in,out,used, l, 0);
 }

 private void doPermute(char[] in, StringBuilder out, boolean[] used, int n,
   int level) {
  if (level==n){
   System.out.println(out.toString());
   return;
  }
  
  for(int i=0;i<n;i++){
   if(used[i]) continue;
   out.append(in[i]);
   used[i]=true;
   doPermute(in, out, used, n, level+1);
   used[i]=false;
   out.setLength(out.length()-1);
  }
  
 }
}

References:

1. Programming Interviews Exposed
2. http://www.paulgriffiths.net/program/c/perm.php