TATA Consultancy Services Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
@Apostle: Question is not clearly written but I think after having a look at your answer the question becomes more clear.
Many solutions work here since 2^7 can express 128 combinations and we need only 100 of those. For example, 50 25 13 6 3 2 1 (and many others) also works. For the above set, calling the bags B1 to B50 based on the value, we have:
C1= B1
C2= B2
C3= B3
C4= B3, B1
C5= B3, B2
C6= B6
C7 to C12 = B6 + C1 to C5
C13= B13
C14 to C24= B13+C1 to C11
C25= B25
C26-49= B25+C1 to C24
C50= B50
C51-C99= B50 + C1 to C49
For the second question, as Apostle pointed out, constraints are needed. Figuring out the constraints turns out to be an interesting problem.
One constraint is clear: if the Guru puts more than 50 gems in his bag no solution is possible. In that case, the remaining bags sum to less then 50 and the Guru's bag has 51 or more. So, we do not have a solution that adds up to 50.
Case 1: If 19 =< xg <= 32 then pick 5 coins as 16, 8, 4, 2 and 1 adding xg and 100-total. Note that for all cases we must have xg and 100-total. xg by definition (the guru pick) and 100-total in the 7th bag is the remaining gems which are needed to enumerate up to 100. So, we have a choice with 5 bags only.
If xg is less than 19 (say 18), then xg + 31 < 50, which means that 100-total is > 50 which leads to an infeasible solution.
For example, if xg = 20, then 1,2,4,8,16, 20 and 49. The first 5 coins can enumerate 1-31. With the 6th coin we can enumerate up to 51. Adding the last coin we can enumerate 1 to 100.
Case 2: by symmetry, if 19 <= 100-total =< 32 then xg can be 37 to 50
Corollary: In the range of 19-50, this leaves xg between 33--36 without a feasible configuration. In this range, the first 5 bags can enumerate up to 31, the remaining 2 bags are needed for xg and 100-total. In the range above, 100-total is between 33 and 36. This leaves the numbers 31 to xg that cannot be assembled.
Case 3: Lets now consider the range 10<= xg <= 16 where an alternative strategy may be used. Use the first 4 bags as 1, 2, 4, 8 which allows us to enumerate 1 to 15. The fifth coin is xg, allowing us to enumerate up to xg+15 (minimum of 25). Pick the sixth coin as 25 and the 7th coin as 50 allowing enumerating of the whole range.
Note that 17 and 18 cannot be used in this strategy as 16 cannot be composed leaving those values as infeasible. Similarly 9 cannot be used since 9 + 15 - 24. The sixth coin must be > 25 or the 7th coin would be > 50. If this is the case, then 25 cannot be assembled (the first 5 coins enumerate 1-24; the next coin is 26).
Case 4: 6<=xg<=8. Pick the first 3 bags as 1, 2 and 4 -- we can enumerate up to 7. Next comes xg which allows us to enumerate 8 to xg+7 (minimum 13). We are left with 3 coins. Pick the coins as 12, 25 and 50 allowing enumeration of the full range.
This leaves 5 as infeasible. xg of 1,2,3 and 4 are all feasible as we demonstrated above.
Summary: we can come up with a feasible distribution for a guru pick of any number less than or equal to 50 with the exception of the following numbers:
5, 9, 17, 18, 33, 34, 35, 36.
I probably made a few mistakes above :-)
#include<iostream>
using namespace std;
int main(){
int maxNumber,gurunum,num=1,binlen=0;
cout<<"enter maxNumber\n";
cin>>maxNumber;
while(num < maxNumber){
num = (num << 1) + 1;
binlen++;
}
int distnum[binlen+1]; //distnum contains distinct maxNumbers by adding these we get any num between 0 to maxNumber(like 100).
cout<<"enter the maxNumber given by guru\n";
cin>>gurunum;
num = num>>1;
if(gurunum != (100 - num)){
num = 1;
while(num < gurunum)
num = (num<<1);
if(num != gurunum){
cout<<"not possible\n";
return 0;
}
}
num=1;
for(int i=0;i<binlen;i++){
//distnum[i] = num;
cout<<num<<" ";
num = (num<<1);
}
num--;
num = 100 - num;
cout<<num<<endl;
return 0;
}
#include<iostream>
using namespace std;
int main(){
int maxNumber,gurunum,num=1,binlen=0;
cout<<"enter maxNumber\n";
cin>>maxNumber;
while(num < maxNumber){
num = (num << 1) + 1;
binlen++;
}
int distnum[binlen+1]; //distnum contains distinct maxNumbers by adding these we get any num between 0 to maxNumber(like 100).
cout<<"enter the maxNumber given by guru\n";
cin>>gurunum;
num = num>>1;
if(gurunum != (100 - num)){
num = 1;
while(num < gurunum)
num = (num<<1);
if(num != gurunum){
cout<<"not possible\n";
return 0;
}
}
num=1;
for(int i=0;i<binlen;i++){
//distnum[i] = num;
cout<<num<<" ";
num = (num<<1);
}
num--;
num = 100 - num;
cout<<num<<endl;
return 0;
}
There may not be a solution in all the cases. But if there exists, this code will print it out.
#define NUM_PURSES 7
void distribute( int total, int alreadyChosen )
{
int result[NUM_PURSES] = {0};
int currentTotal = 0;
int next_count = 1;
bool consumed = false;
for( int i = 0; i < NUM_PURSES; i++ )
{
if( ( !consumed ) && ( next_count >= alreadyChosen ) )
{
next_count = alreadyChosen;
consumed = true;
}
if( ( next_count + currentTotal ) > total )
next_count = total - currentTotal;
result[i] = next_count;
currentTotal += result[i];
next_count = currentTotal + 1;
}
for( int i = 0; i < NUM_PURSES; i++ )
std::cout << result[i] << std::endl;
}
The seven bags should have the gems distributed in the following way.
- Murali Mohan August 14, 20131, 2, 4, 8, 16, 32 & 37
The other part of the question where the teacher can put any number of gems in one purse and asking the student to distribute the rest is invalid. What if the teacher puts all of the 100 gems in one bag? In such a case the student will not be able to distribute the gems and will also not be able to give gems of the required number.