Rahul is playing a very intere

Interview Question

0

of 0 votes

9
Answers
Rahul is playing a very interesting game. He has some N different type of match boxes. All match boxes may have different number of matchsticks (S1, S2, S3... Sn).

Rahul chooses two random numbers F and K. K should be less than N. The game is that Rahul wants to select any K match boxes out of N match boxes such that total number of matchsticks in these K selected match boxes should be multiple of F.
At the sametime Rahul wants that sum matchsticks of all the selected match boxes should be minimum possible.

Input Specifications:
1) Array S = {S1,S2,S3,...Sn} of size N corresponding to the number of match sticks in N matchboxes(0<=N<=1000}
2) F-Value (as explained above)
3) K-Value ( as explained above)

Output:
1 2 3 4 5 Here 3 is the number of matchsticks in matchbox I II III IV V minimum possible total number of matchsticks such that the conditioned explained in the problem statement is satisfied. Output -1 if it is not possible or invalid input.

For example, there are 5 match boxes i.e., N = 5
Let's say K is 3 (Rahul has to choose any 3 matchboxes)

Let's say F is 5(sum of matchsticks in 3 selected matchboxes should be multiple of 5).
Rahul can choose II, III and V matchboxes which would give the total sum of 10 which is multiple of F i.e., 5. And 10 is the minimum possible matchsticks possible in the above case.
So you have to answer the minimum possible matchstick(sum of the matchsticks in the selcted matchboxes) but the conditions given above should be satisfied.
- veeru April 29, 2015 in India | Report Duplicate | Flag | PURGE
Algorithm

Email me when people comment.

An error occurred in subscribing you.

Country: India
Interview Type: Phone Interview

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 0 vote

public static int match_sticks(int[] input1, int input2, int input3) {
int sumArray []= new int[2000];
int N = input1.length;
if (input3 > N) {
return -1;
}
int combination[] = new int[input3];
int r = 0;
int index = 0;
int i=0;
while (r >= 0) {
if (index <= (N + (r - input3))) {
combination[r] = index;
if (r == input3 - 1) {
int sum=0;
for(int l=0;l<combination.length;l++){
sum=sum+input1[combination[l]];

}
if(sum%input2==0){
sumArray[i]=sum;
i++;
}

index++;
} else {
index = combination[r] + 1;
r++;
}
} else {
r--;
if (r > 0)
index = combination[r] + 1;
else
index = combination[0] + 1;
}

}

int finalSum=sumArray[0];
if(finalSum==0){
finalSum=-1;
}else{
for(int j=1;j<sumArray.length;j++){
if(sumArray[j]==0){
break;
}
if(finalSum>sumArray[j]){
finalSum=sumArray[j];
}
}
}
return finalSum;
}

- Neha April 30, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public static int match_sticks(int[] input1, int input2, int input3) {
		int sumArray []= new int[2000];
		int N = input1.length;
		if (input3 > N) {
			return -1;
		}
		int combination[] = new int[input3];
		int r = 0;
		int index = 0;
		int i=0;
		while (r >= 0) {
			if (index <= (N + (r - input3))) {
				combination[r] = index;
				if (r == input3 - 1) {
					int sum=0;
					for(int l=0;l<combination.length;l++){
						sum=sum+input1[combination[l]];
						
					}
					if(sum%input2==0){
						sumArray[i]=sum;
						i++;
					}
					
					index++;
				} else {
					index = combination[r] + 1;
					r++;
				}
			} else {
				r--;
				if (r > 0)
					index = combination[r] + 1;
				else
					index = combination[0] + 1;
			}
			
		}
		
		
		
		int finalSum=sumArray[0];
		if(finalSum==0){
			finalSum=-1;
		}else{
			for(int j=1;j<sumArray.length;j++){
				if(sumArray[j]==0){
					break;
				}
				if(finalSum>sumArray[j]){
					finalSum=sumArray[j];
				}
			}
		}
		return finalSum;
	}

- Neha April 30, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

Could you please explain the logic of your code and/or add comments to it for clarity?

- Killedsteel May 03, 2015 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

this code is not working

- Yogesh May 01, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

- Anonymous November 19, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

this code helped me a lot, thank you

- raji.yemineni January 24, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

how to code using functions in c the same logic

- princy February 12, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

can anyone explain the logic of this algrthm

- javeria011 February 19, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

can anyone explain the logic of this algrthm

- javeria011 February 19, 2017 | Flag Reply

CareerCup

Interview Question

Books

Videos

Resume Review

Mock Interviews