CODEWITHSUNDEEP
algorithmmathdata-structures
Hemant Bhargava
Hemant Bhargava

Reputation: 3585

Predict the number from addition of numbers

Somebody asked me this algorithmic question and as usual, I failed to answer this. :) Let us say, you have one number (call it a)

504

Next time, you see it, you delete the last digit of the number. It becomes (call it b)

50

Next time, you see it, you delete the last digit of the number. It becomes (call it c)

5

Now, add all of the three numbers(a+b+c). It becomes :

504 + 50 + 5 = 559

Alright, by now you might have understand the problem statement quite well.

Question is : Given the addition of three numbers a + b + c to you(in this case 559), how can you go back to the original number(in this case 504)? All solutions would be appreciated.

Upvotes: 1

Views: 109

Answers (2)

ShreevatsaR
ShreevatsaR

Reputation: 39083

Suppose the number you started with looks like xyz. That is, its last (decimal) digit is z, its penultimate digit is y, and the rest is x. In your example, if you started with 504, then x=5, y=0, z=4. The value of your original number is 100x+10y+z.

The number you end up with is the sum of (100x+10y+z), (10x+y), and x. This is 111x+11y+z.

Note that our constraints were that 0≤y≤9 and 0≤z≤9. Even with their largest values, we have 11y+z ≤ 11(9) + 9 < 111. So we can invert the transformation: pull out the largest multiple of 111, then pull out the largest multiple of 11 from the remaining, and then what's left.

def transform(n):
    return n + (n/10) + (n/100)

def invert(m):
    [x, y, z] = [m/111, (m%111)/11, (m%111)%11]
    return 100*x + 10*y + z

assert transform(504) == 559 
assert invert(559) == 504

(Try the above in a Python shell. Note that this works even if x is not a single-digit number: transform(12345) gives 13702, and invert(13702) gives 12345, as expected.)

Edit: An alternative solution, based on the idea in Paul Hankin's answer (please upvote it) of using m*100/111 as a starting point. You can certainly use (the ceiling of) that value as a rough answer and try adding 1 and 2 to get the exact answer, but you can also precompute the "offset" needed from the rough answer.

# Precomputation, to populate the "offset" dictionary
def sane_mod(a, m): return ((a % m) + m) % m
offset = {}
for y in range(10):
    for z in range(10):
        add = 10*y + 11*z
        offset[sane_mod(-add, 111)] = add

# Actual function
def invert2(m):
    rough = m * 100
    return (rough + offset[rough % 111]) / 111
assert invert2(559) == 504

Upvotes: 2

Paul Hankin
Paul Hankin

Reputation: 58271

a+b+c is a + a//10 + a//100 (where // denotes rounding-down division). This is somewhere between a * 111/100 - 1.89 and a * 111/100. (1.89 because the maximum fraction discarded from a//10 is 0.9 and the maximum fraction discarded from a//100 is 0.99, and 1.89 = 0.9 + 0.99).

So, given a+b+c, we're looking for integer a such that:

a * 111/100 - 1.89 <= a + b + c <= a * 111/100
a - 2.0979 <= (a + b + c) * 100 / 111 <= a

Thus, let x = ceil((a + b + c) * 100 / 111), and one of x, x+1 or x+2 must be the solution.

Upvotes: 1

Related Questions