## 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.