HackerRank Algebra – Calculate It

Challenge: Calculate It

Subdomeniu: Algebra (algebra)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464811685

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/calculate-it/problem

Cerinta

Little Tom loves to solve interesting math challenges. One day he bumped onto an interesting function called _hRank_.  
Given a positive integer **k**, _hRank_ maps a non-negative integer **x** to another integer.


    hRank(x) = 1 if 0 <= x < k
    hRank(x) = hRank(x – k) + hRank(x / k) if x >= k and k | x  (i.e., x modulo k = 0)
    hRank(x) = hRank(x – 1) otherwise.

Because  x  and hRank(x) may be very large, Tom comes to you for help. Given k and x, can you calculate hRank(x)?

**Input Format**  
The input contains only one line with 2 space separated integers, k and x.

**Output Format**  
For each test case output the result in a single line.

**Constraints**  
2 <= k <= 10   
1 <= x <= k<sup>50</sup>  

**Sample Input #00**

    2 1

**Sample Output #00**

    1

**Sample Input #01**

    3 9

**Sample Output #01**

    5

**Explanation**

For the first sample input, when k = 2 and x = 1, the answer is 1 since hRank(x) = 1 as 1 < 2  
For the second sample input, when k = 3 and x = 9, we have 

    hRank(9) = hRank(9-3) + hRank(9/3)  = hRank(6) + hRank(3) as 9 > 3 and 9 modulo 3 = 0. 
    hRank(6) = hRank(6-3) + hRank(6/3) = hRank(3) + hRank(2) as 6 > 3 and 6 modulo 3 = 0. 
    hRank(3) = hRank(3-3) + hRank(3/3)  = hRank(0) + hRank(1) as 3 >=3 and 3 modulo 3 = 0. 
    hRank(3) = hRank(0) + hRank(1)
    hRank(3) = 1 + 1 = 2
    hRank(6) = 2 + 1 = 3
    hRank(9) = 3 + 2 = 5

Cod sursa

#!/bin/python3

from math import comb

#
# Complete the 'solve' function below.
#
# The function is expected to return a STRING.
# The function accepts following parameters:
#  1. INTEGER k
#  2. STRING x
#

def _to_base_k(n, k):
    if n == 0:
        return [0]
    d = []
    while n > 0:
        n, r = divmod(n, k)
        d.append(r)
    return d  # little-endian


def solve(k, x):
    n = int(x)
    digits = _to_base_k(n, k)
    L = len(digits)

    # B_i[p] = sum_c F_i(c) * C(c, p),
    # where F_i(c) counts valid carry suffixes from digit i upward.
    # We need F_0(0), which equals B_1[0].
    Q = L
    B_next = [0] * (Q + 2)
    B_next[0] = 1  # F_L is delta at carry 0.

    # Process digits d_{L-1} ... d_1 (d_0 does not affect F_0(0)).
    for i in range(L - 1, 0, -1):
        di = digits[i]
        B_cur = [0] * (Q + 2)

        for p in range(Q + 1):
            deg = p + 1

            # f(t) = C(di + k*t + 1, p+1), t=0..deg
            vals = [comb(di + k * t + 1, p + 1) for t in range(deg + 1)]

            # Expand in binomial basis C(t,q) via forward differences:
            # f(t) = sum_q Delta^q f(0) * C(t, q)
            coeff = [0] * (deg + 1)
            for q in range(deg + 1):
                coeff[q] = vals[0]
                for t in range(deg - q):
                    vals[t] = vals[t + 1] - vals[t]

            s = 0
            qmax = min(deg, Q + 1)
            for q in range(qmax + 1):
                s += coeff[q] * B_next[q]
            B_cur[p] = s

        B_next = B_cur

    return str(B_next[0])


if __name__ == '__main__':
    import sys

    first_multiple_input = sys.stdin.readline().rstrip().split()
    k = int(first_multiple_input[0])
    x = first_multiple_input[1]

    result = solve(k, x)
    sys.stdout.write(result + '\n')