Interview Question
Country: United States
you are right, the only requirement is that one character maps to *one* digit but it is not necessary that one digit corresponds to one character.
This is a quite natural thing to assume because there are more characters (26) than digits (10). Otherwise some puzzles would not be solvable
I think the only way to solve this problem is to use recursive bruteforce approach.
We start assigning digits to characters of both strings 'X' and 'Y' one-by-one.
that is, X[0] and Y[0]
X[1] and Y[1] and so on.
Every time we assign some X[i] and Y[i] we also check if the sum equals to Z[i].
If not, we do not need to further exploit this recursive path.
Here is the program:
// strings to be assigned: s3 = s1 + s2
const char *s1 = "abcd", *s2 = "badc", *s3 = "cdab";
// which = 0: assign the i-th character of string 's1'
// which = 1: assign the i-th character of string 's2'
// carry: carry flag for integer addition
void assign(int i, int which, int carry) {
// assign the i-th character of the 1st number
if(which == 0) {
if(i == -1) { // all combinations checked
if(carry == 1)
return;
for(int j = 0; j < l1; j++) {
printf("%d", A[s1[j] - 'a']);
}
printf(" + ");
for(int j = 0; j < l2; j++) {
printf("%d", A[s2[j] - 'a']);
}
printf(" = ");
for(int j = 0; j < l3; j++) {
printf("%d", A[s3[j] - 'a']);
}
printf("\n");
return;
}
int i1 = s1[i] - 'a';
if(A[i1] != -1) {
assign(i, 1, carry); // assign i-th digit of 2nd no
}
for(int d = 0; d < 10; d++) {
A[i1] = d;
assign(i, 1, carry);
}
A[i1] = -1;
return;
}
// assign the i-th character of the 2nd number
int x1 = A[s1[i] - 'a']; // s1 already assigned
int i2 = s2[i] - 'a';
int i3 = s3[i] - 'a';
if(A[i2] != -1) {
int sum = A[i2] + x1 + carry;
int c1 = sum / 10;
sum %= 10;
if(A[i3] != -1) { // mismatch
if(A[i3] != sum)
return;
return assign(i - 1, 0, c1);
}
A[i3] = sum;
assign(i - 1, 0, c1);
A[i3] = -1;
return;
}
for(int d = 0; d < 10; d++) {
A[i2] = d;
int sum = A[i2] + x1 + carry;
int c1 = sum / 10;
sum %= 10;
if(A[i3] != -1) { // mismatch
if(A[i3] != sum)
continue;
assign(i - 1, 0, c1);
} else {
A[i3] = sum;
assign(i - 1, 0, c1);
A[i3] = -1;
}
}
A[i2] = -1;
}
results (some of them repeated twice):
8089 + 0898 = 8980
7189 + 1798 = 8971
7189 + 1798 = 8971
6289 + 2698 = 8962
6289 + 2698 = 8962
5389 + 3598 = 8953
5389 + 3598 = 8953
4489 + 4498 = 8944
4489 + 4498 = 8944
3589 + 5398 = 8935
3589 + 5398 = 8935
2689 + 6298 = 8926
2689 + 6298 = 8926
1789 + 7198 = 8917
1789 + 7198 = 8917
0889 + 8098 = 8908
0889 + 8098 = 8908
0449 + 4094 = 4904
2359 + 3295 = 5923
1459 + 4195 = 5914
0559 + 5095 = 5905
4269 + 2496 = 6942
3369 + 3396 = 6933
2469 + 4296 = 6924
1569 + 5196 = 6915
0669 + 6096 = 6906
6179 + 1697 = 7961
5279 + 2597 = 7952
4379 + 3497 = 7943
3479 + 4397 = 7934
2579 + 5297 = 7925
1679 + 6197 = 7916
0779 + 7097 = 7907
8089 + 0898 = 8980
8089 + 0898 = 8980
7189 + 1798 = 8971
7189 + 1798 = 8971
6289 + 2698 = 8962
6289 + 2698 = 8962
5389 + 3598 = 8953
5389 + 3598 = 8953
4489 + 4498 = 8944
4489 + 4498 = 8944
3589 + 5398 = 8935
3589 + 5398 = 8935
Can you explain the question bit clearer?
- howaboutthis April 20, 2012here a maps 2, b maps 2, c maps to 7, d maps 5, which means each character can mapping is not unique like a & b both are 2.