Home > other >  Find the minimum number of moves for Sum(A) <= B
Find the minimum number of moves for Sum(A) <= B

Time:08-01

You are given two non-negative integers A and B. Let the function Sum(A) be the sum of digits of the number A. You can perform any number of moves (possibly zeros).

  • In one move you can increase the value of A by 1.

Find the minimum number of moves you have to perform to make sum(A) <= B.

Constraints:

1 <= A <= 10^12

1 <= B <= 108

Sample Test Cases:

1. A = 1, B = 1       Output = 0
2. A = 9, B = 2       Output = 1
3. A = 555, B = 10    Output = 45
  • Inputs are given in string.

How to solve this problem in python?

Here is the code I have tried:

def countmoves(A, B):

    int_A = int(A)
    int_B = int(B)
    count = 0
    
    while True:
        digits = [int(i) for i in str(int_A)]
        s_m = sum(digits)
        if s_m <= int_B:
            print(f"count: {count}")
            return count
        else:
            int_A  = 1
            count  = 1

But my code is getting Timed Out. How can I optimize it?

CodePudding user response:

You could do it by finding the rightmost non-zero number and adding a value such that the element to the left is increased by 1 and all to the right (inclusive) become 0:

def countmoves(A, B): #nin17()
    count = 0
    B = int(B)
    while True:
        total = sum(int(i) for i in A)
        if total <= B:
            return count
        else:
            index = max(A.rfind(i) for i in ['1', '2', '3', '4', '5', '6', '7', '8', '9'])
            right = A[index:]
            moves = 10**len(right)-int(right)
            A = f'{int(A) moves}'
            count  = moves

Or with a for loop instead, looping from right to left through A:

def countmoves(A, B): #nin172()
    count = 0
    B = int(B)
    for i, j in enumerate(range(len(A)-1, -2, -1), 1):
        total = sum(int(i) for i in A)
        if total <= B:
            return count
        else:
            moves = 10**i-int(A[j:])
            A = f'{int(A) moves}'
            count  = moves

Timings (with given test cases):

for A, B in (('1', '1'), ('9', '2'), ('555', '10')):
    %timeit op(A, B)
    %timeit nin17(A, B) #while
    %timeit nin172(A, B) #for

Output:

600 ns ± 9.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) #OP
473 ns ± 2.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) #Nin17 while
732 ns ± 1.94 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) #Nin17 for
1.12 µs ± 8.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) #OP
2.6 µs ± 44.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) #Nin17 while
1.58 µs ± 2.49 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) #Nin17 for
26.6 µs ± 63.3 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each) #OP
5.18 µs ± 7.37 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) #Nin17 while
2.89 µs ± 17.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) #Nin17 for

Timings with larger values:

A = '363513974325'
B = '28'
assert op(A, B) == nin17(A, B)
assert nin17(A, B) == nin172(A, B)
%timeit op(A, B)
%timeit nin17(A, B)
%timeit nin172(A, B)

Output:

45.2 ms ± 66.4 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) #OP
19.3 µs ± 197 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) #Nin17 while
12.2 µs ± 18.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) #Nin17 for

CodePudding user response:

def digit_sum(A):
    return sum(list(map(int, str(A).strip())))

def countmoves(A, B):
    final_moves = 0
    place_holder = 0

    while digit_sum(A) > B:
        place_holder  = 1
        remainder = A % (10 ** place_holder)
        if (remainder):
            moves = (10 ** place_holder) - remainder
            A = A   moves
            final_moves  = moves

    return(final_moves)
  • Related