# Programming Problems 4

October 3, 2009 8 Comments

**1. Power of 3**

Given M, find if M = 3^x for some positive integer x efficiently. DO NOT think of log, pow etc.

**2. Maximum Sum path in a Matrix**

Given a M*N matrix A. Find a path from the top-left element (ie A[0][0]) to the bottom right element (ie A[M-1][N-1]) such that the sum of the elements in the path is maximum. Length of path should be M + N – 1. Moves can be made towards the right and bottom only by 1 cell i.e. from A[i][j] only two possible steps are A[i+1][j] or A[i][j+1].

**3. Longest Interval with Maximum Sum**

We are given with two arrays A and B..each of size N…elements of array contains either 1 or 0. We have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal. i.e. a[p]+a[p+1]….+a[q]= b[p]+b[p+1]….+b[q]. Solution should be better than O(n^2)

**4.Divide the array into groups**

Divide a list of numbers into groups of consecutive numbers but their original order should be preserved.

Example:

<8,2,4,7,1,0,3,6>

Two groups:

<2,4,1,0,3> <8,7,6>

Better than O(n^2) is expected.

**5. Sort on second key when array is sorted on first key**

Assume that we are given as input n pairs of items, where

- the first item is a number
- the second item is one of three colors (red, blue, or yellow).

Further, assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

5. we can solve the problem using chain hashinh. take a hash map of three and traverse the array. if element is of red colour.. append it to hash[0] if u blue then to hash[1] else to hash[2]..

now print the result by traversing through hash . 1st print all elements of hash[0] by traversing linked list at hash[0]..when we reach null ( end of hash[0] ) then traverse hash[1] and then hash[2].

time O(n)

is correct 🙂

A different approach is still possible where you can solve it in-place i.e. without using the extra space for hashing, by just re-arranging the elements in the array in O(n) time.

I am unable to figure out inplace method.. 😦 can u please enlighten me with it?

4.

sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group..and maintain the index along with every element.

now we need to rearrange elements in the group by sorting them on the basis of their index.

time O(nlogn)

didn’t get you. can u give a pseudo code / compiling code (preferable) ?

@divya

5. just count the number of red, blue and greens and then figure out a way. This approach works because there are only 3 distinct values for second pair.

1. write number M in base-3, and check if it contains only one digit(1)

5 I think you are refering to Dutch national flag algo for 3 elements. but that will change the order of nos. ie it will make the colour sorted but nummbers within the same colour may not remain sorted. and then we have to sort the numbers again. I think hashing technique should be apt here. Please correct me if i am wrong.

4. pseudocode

divideInGroups(int a[],int n) {

int index[n];

for(i=0;i<n;i++)

index[i]=i;

sort(a,n,index); //use any sorting O(nlogn) algorithm to sort the array. and while changing the position of number change its index according.. for eg if the initial array was a={ 8,2,4,7,1,0,3,6} and index[] was = {0,1,2,3,4,5,6,7} after sort function a[] will be= {0,1,2,3,4,6,7,8} and index[] will be {5,4,1,6,2,7,3,0}

// now we have to divide into groups 🙂

i=0;

while(i<n)

{

while(a[i+1]=a[i]+1)

{

insert in same group (make a link list perhaps for a group)

i++;

}

sort the group (linked list ) according to index[] array

print the group

i++;

}

}

#include

using namespace std;

void main()

{

int pow=1;

cout<>M; // as m is

for(int i=0;i<=50;i++) // 50 is arbitary limt

{

pow= pow* 3;

if(M==pow)

{

x= i;

break;

}

}

cout<<x;

}