CODEWITHSUNDEEP
algorithmencoding
piternet
piternet

Reputation: 315

Decode number coded with some strange algorithm

There is such an encoding algorithm: we're given some number x, let's say 7923. We add zeros to the end and the beginning of it - 079230. Now we sum digits, beginning from the right side - the first digit with the second, the second with the third etc. If the sum is bigger than 9, we subtract 10 from it and move 1 to the next operation.

So for the example of 079230: 0+3 = 3, 3+2=5, 2+9=11, 9+7+1=17, 7+0+1=8. Our encoded number are the results of the operations, so we end with a number: 87153.

Now, we are given the encoded number, but with one digit missing - for example 871X3. Now we need to decode it - get 7923 from it.

So shortly speaking - 871X3 is the input, the output should be 7923. Only one digit could be missing.

That is kind of weird problem for me. I guess we need to deduce somehow the original number, maybe with some backtracking? The first digit of original number could be the first digit of encoded number or that digit minus 1. But I can't see any path leading from here to the solution.

Upvotes: 0

Views: 450

Answers (2)

Prune
Prune

Reputation: 77857

Look at your algorithm: this is merely performing long multiplication. The "encoded" number is the original times 11.

Since the multiplier is greater than 9, there can be only one possibility for the missing digit. Find it with modular arithmetic. Put in 0 as the missing digit and check:

87103 mod 11 ==> 5

Now, the "parity" of the number changes with the position. Counting from the right, even-numbered positions will return the missing digit itself (factors of 0, 99, 9999, 999999, etc. will drop out). Odd-numbered positions will give the additive inverse: subtract that digit from 11 to get the missing one. For the given example, try this for each of the digits:

87150 mod 11 ==> 8  missing digit is 3 (11-8)
87103 mod 11 ==> 5  missing digit is 5
87053 mod 11 ==> 10 missing digit is 1 (11-10)
80153 mod 11 ==> 7  missing digit is 7
 7153 mod 11 ==> 3  missing digit is 8 (11-3)

Upvotes: 1

Dave
Dave

Reputation: 9085

say the digits of the original number are, from left to right, d,c,b,a.

0 + a mod 10 = 3, so a = 3
3 + b mod 10 = 5, so b = 2
2 + c mod 10 = 1, so c = 9
9 + 1 + d mod 10 = 7, so d = 7
7 + 1 mod 10 = 8, as expected.

Upvotes: 0

Related Questions