There are several solutions to this particular sequence!
Code:
100+2+34+1+90 = 227
(the above found in loop #54)
10+023+4+190 = 227
(the above found in loop #76)
10+0+23+4+190 = 227
(the above found in loop #108)
1+002+34+190 = 227
(the above found in loop #148)
1+00+2+34+190 = 227
(the above found in loop #180)
1+0+02+34+190 = 227
(the above found in loop #212)
1+0+0+2+34+190 = 227
(the above found in loop #244)
And the routine.
Code:
#include <stdio.h>
#include <math.h>
#include <string.h>
int test_solution(char * number, char * total, int value) ;
int getsum(char * expression) ;
int main(void) {
char user_string[] = "100234190" ;
char user_sum[] = "227" ;
// Calculate the max loops we need to process
int maxloops = (int) pow(2.0, (double) strlen(user_string)-1) ;
int i ;
int result ;
int found = 0 ; // flag
for (i = 1 ; i <= maxloops ; i++) {
result = test_solution(user_string,user_sum,i) ;
if (result) {
found = 1 ;
printf("\t(the above found in loop #%d)\n", i) ;
//break ; // uncomment this to stop at the first solution
}
}
if (!found) printf("No solution\n") ;
return 0 ;
}
int test_solution(char * number, char * total, int value) {
int i ;
int sum = atoi(total) ;
int number_index ;
char expression[21] ;
char local_number[21] ;
char * expression_ptr ;
strcpy(local_number,number) ;
for (i = 0 ; i < sizeof(expression)-1 ; i++) expression[i]=0 ; // clear workarea
number_index = strlen(local_number)-1 ;
expression_ptr = expression + (strlen(local_number)*2) - 1 ; // work right to left
// Using the bit pattern in "value", insert a plus sign at each binary 1.
while(value != 0) {
*expression_ptr-- = local_number[number_index] ;
local_number[number_index--] = 0 ; // truncate it
if (value & 1) {
*expression_ptr-- = '+' ;
}
value >>= 1 ;
}
// Copy remainder of the number (left-most part) into the expression
for (i = number_index ; i >=0 ; i--) *expression_ptr-- = local_number[i] ;
if (getsum(expression_ptr+1) == sum) {
printf("%s = %d\n", expression_ptr+1, sum);
return 1 ;
}
return 0 ;
}
int getsum(char * expression) {
int total = 0 ;
char * plus_position ; // position of the plus sign
char * current_pointer = expression ;
while (1) {
plus_position = strchr(current_pointer, '+') ;
if (plus_position==NULL) { // add the last number
total += atoi(current_pointer) ;
return total ;
}
*plus_position = 0 ;
total += atoi(current_pointer) ;
*plus_position = '+' ;
current_pointer = plus_position+1 ;
}
}