7 months ago+ 0 comments

My Python Loopless Solution

With Derivation of Answer

def solve(a, n, m):
	digits = len(str(a))
	divisor = 10**digits-1
	m *= divisor
	return (a % m)*(pow(10, digits*n, m)-1) % m // divisor

Explanation

$\\ 1.\text{ } (a+m) \text{ % } m = a \text{ % } m \\ \\ 2. \text{ } (a+b) \text{ % } m = (a \text{ % } m + b\text{ % } m) \text{ % } m \\ \\ 3.\text{ } ab \text{ % } m = (a \text{ % } m)(b \text{ % } m) \text{ % } m \\ \\ 4.\text{ } \frac {a}{b} \text{ % } m = \frac {a \text{ % } bm}{b} \\ \\ \text {Let len(a)} = \text {the digits in a} \\ \\ \frac {10^{\text {len(}a)}}{a}s = 10^{\text {len(}a)}+...+10^{\text {len(}a)(n-1)}+10^{\text {len(}a)n} \\ \\ \frac {1}{a}s= 10^{0}+10^{\text {len(}a)}...+10^{\text {len(}a)(n-1)} \\ \\ \frac {10^{\text {len(}a)}-1}{a}s = 10^{\text {len(}a)n}-1 \\ \\ s = a\frac {10^{\text {len(}a)n}-1}{10^{\text {len(}a)}-1} \\ \\ \text {Let } b = 10^{\text {len(}a)}-1 \\ \\ s \text{ % } m = \frac {(a \text{ % } bm)((10^{\text {len(}a)n}-1) \text{ % } bm) \text{ % } bm}{b} \\ \\ (10^{\text {len(}a)n}-1) \text{ % } bm = ((10^{\text {len(}a)n} \text{ % } bm) + (-1) \text{ % } bm ) \text{ % } bm)$ $\\ a^{b} \text { % } m = \text {pow(a, b, m)} \text { in python} \\ \\ (-1) \text { % } m = (-1+m) \text { % } m \\ \\ (-1) \text { % } m = m-1 \quad \text {Since }bm-1< m \\ \\ (10^{\text {len(}a)n}-1) \text { % } bm = (\text {pow(a, \text {len(}a)n, bm)}+bm-1) \text { % } m \\ \\ \text {pow(a, \text {len(}a)n, bm)} - 1< bm \text { and adding }bm \text { has no effect so:} \\ \\ (10^{\text {len(}a)n}-1) \text { % } m = \text {pow(a, \text {len(}a)n, bm)}-1 \\ \\ s \text { % } m = \frac {(a \text{ % } bm)(\text {pow(a, \text {len(}a)n, bm)}-1) \text{ % } bm}{b}$

My Python Loopless Solution

Explanation

Cookie support is required to access HackerRank