ak
BAN USERMy Idea is to release for the side which results in maximum isolation
int findGoldCoinCount(int startIndex, int endIndex, const int *prisoners, int prisonerCount){
int goldCount = endIndex - startIndex - 1;
if(prisonerCount <= 1) {
printf("gold count=%d release %d\n",goldCount, prisoners[0]);
return goldCount;
}
prisonerCount--;
int startDiff = prisoners[0] - startIndex;
int endDiff = endIndex - prisoners[prisonerCount];
if(startDiff > endDiff){
printf("gold count=%d release %d\n",goldCount, prisoners[0]);
goldCount += findGoldCoinCount(prisoners[0]+1, endIndex, prisoners+1, prisonerCount);
} else {
printf("gold count=%d release %d\n",goldCount, prisoners[prisonerCount]);
goldCount += findGoldCoinCount(startIndex, prisoners[prisonerCount]-1, prisoners, prisonerCount);
}
return goldCount;
}
for input 11111, there are 8 combinations
{1,1,1,1,1}, {11,1,1,1},{1,11,1,1}, {1,1,11,1},{1,1,1,11}, {1,11,11}, {11,1,11}, {11,11,1}
here is my program
int findDecodeCombinationCount(char *string){
if(*string == '\0'){
return 1;
} else if(*string <= '0' || *string > '9'){
printf("DECODE ERROR, invalid input !!\n");
return 0;
} else if(*(string+1) == '\0') {
return 1;
} else if (*(string+1) == '0'){
return findDecodeCombinationCount(string+2) ;
} else if((*string > '2') || ((*string == '2') && (*(string+1) > '6'))){
return findDecodeCombinationCount(string+1) ;
} else {
return findDecodeCombinationCount(string+1) + findDecodeCombinationCount(string+2);
}
}
non recursive version of the same
- ak May 17, 2016