Microsoft Interview Question
Software Engineer in TestsCountry: India
For the same question (x1+x2+x3+x4+X5=20), if only non-zero non-negative integrals(natural numbers) were allowed, then we can formulate it as follows.
In such a case the number of solutions reduce to the number of ways in which we can make 5 partitions by drawing four lines in between
1111111111111111111 (20 1's.)
We can sum up each partition independently. This avails, any 4 locations (for 4 lines) amongst 19 gaps(between 20 1's there are 19 gaps, where we draw the lines.)
Therefore the answer is 19C4.
Using the above idea we can deduce that if 0's are allowed, then the number of combinations increases to 24C4.(Because we can keep the lines together as well.)
can we find the substructure . i dont think that this problem has substructure property .
we dont need 5 loops ,we can do in just 4 loops.
int find()
{
int total=0;
for(int i=0;i<=num;i++)
{
for(int j=0;j<=num;j++)
{
if(i+j>num)
break;
for(int k=0;k<=num;k++)
{
if(i+j+k>num)
break;
for(int m=0;m<=num;m++)
{
if(i+j+k+m>num)
break;
cout<<"\n"<<i<<" "<<j<<" "<<k<<" "<<m<<" "<<num-i-j-k-m;
total++;
}
}
}
}
return total;
}
Four loops five loops.Seriously??
Use recursion..
If u have to fit 20 in x1 -x5,
give pos =5 and n=20 to following program
int FindSol(int pos, int n)
{
int sum =0;
if(pos == 1)
{
return 1;
}
if(n == 0)
{
return 1;
}
for(int i= n;i > 0;i--)
{
sum = sum + FindSol(pos -1,i);
}
return sum + 1;
}
#include<stdio.h>
static int findNumSoln(int var, int desiredSum)
{
int totalSoln = 0;
/* assert (desiredSum>=0); */
if (var == 1 && desiredSum >=0) { return 1; }
for (int i =0 ; i<=desiredSum ; i++) {
totalSoln += findNumSoln(var-1, desiredSum-i);
}
return totalSoln;
}
int main ()
{
int var = findNumSoln(5, 20 ) ;
printf ("total num soln = %d\n", var);
return 0;
}
If the problem is this simple why not a nested loop. Have five loop variables going from 0 to 20. Print the loop variables if the current sum is 20.
for ( int i = 0; i <= 20; ++i )
for ( int j = 0; j <= 20; ++j )
for ( int k = 0; k <= 20; ++k )
for ( int l = 0; l <= 20; ++l )
for ( int m = 0; m <= 20; ++m )
{
if ( (i + j + k + l + m) == 20 )
{
printf( "(%d %d %d %d %d %d) \n" , i , j , k , l , m );
}
}
Anonymous, thanks for the code. But this question was asked as an objective question in a written test with options(i don't recall them. they were in the range of 10,000+) for the number of solutions. So there has to be a way we can work that out on paper.
@devanharikumar89: you said that this problem should be solvable
by pensil-and-paper ?
meaning that there is a simple formula for the number of solution
do you remember what was the answer ?
I suspect it should be: 21*22*23 = 10626 ?
Yup, I think we are asked to write down the solution number rather than develop some efficient code to count it. 23*22*21 should be the right answer.
DP:
- wave October 20, 20111. For any element, it can be 0 or non-0.
a. if 0, the number should be n-1 element.
b. if non-0, it can be 1..n. Then the n-1 sum of other n-1 should be 20-num
and merge it together:
int FindNumber(int n, int sum)
{
int tmpSum = 0;
//base
if (n == 1) return 1;
if (n == 0 ) return 0;
for (int i = 0; i<n; i++)
{
for (int j = 0; j<sum; j++)
tmpSum += FindNum(n-1, sum-j);
}
}