Let's solve one problem from codeforces today. (problemset/problem/1766/A)
Problem Statement:
It is a question of 800 rating on CF, if you have not tried it go and try problemset/problem/1766/A first.
Let's discuss the solution now:
a positive integer extremely round if it has only one non-zero digit. For example, 50005000, 44, 11, 1010, 200200 are extremely round integers; 4242, 1313, 666666, 7777, 101101 are not.
so let's define a function which will take a integer n as an input and return is it a extremely round integer or not.
def is_round(n):
digits = list(map(int, str(n)))
return digits.count(0) == (len(str(n)) - 1)
Now the idea is for each test case t we will iterate and find the number of extremely round integer for it.
def main():
t = int(input())
for _ in range(t):
n = int(input())
count_of_round = 0
for i in range(n+1):
if is_round(i):
count_of_round += 1
print(count_of_round)
main()
but the problem is:
Let's go through the PS once again:
n(1<=n<=999999)
let's take the advantage of this limit: We already know n
can't go beyond 999999
. and we are calculating the number of extremely round integers from 0 to n for each number n. let's memorize this answers. I will take a array named dp
and store answers(k)
from 0 to 999999
in the dp array. when a new n comes we will access the specific index and return the specific answer.
dp = [0]
for i in range(1, 999999+1):
if is_round(i):
dp.append(dp[len(dp)-1] + 1)
else:
dp.append(dp[len(dp)-1])
Let's write the complete code:
def is_round(n):
digits = list(map(int, str(n)))
return digits.count(0) == (len(str(n)) - 1)
def main():
dp = [0]
for i in range(1, 999999+1):
if is_round(i):
dp.append(dp[len(dp)-1] + 1)
else:
dp.append(dp[len(dp)-1])
t = int(input())
for _ in range(t):
n = int(input())
print(dp[n])
main()
result:
- Time Complexity of each test case = O(10⁷)
- Space Complexity of each test case = O(10⁷)
- Time Complexity = O(t*10⁷)
- Space Complexity = O(t*10⁷)
But we can still do better, Intuition: every interval of (n+1) and (n)*10 have exactly 9 extremely round.
For example: 11 to 100 have exactly 9 extremely round integer - 20, 30, 40, 50,60 70, 80, 90, 100.
And every interval of ((i*10)+1) and ((i+10)*10) have exactly 1 extremely round integer.
Example: 201 to 300 we have only one extremely round integer - 300.
def main():
t = int(input())
for _ in range(t):
n = int(input())
m = 1
ans = 0
while m*10<n:
ans += 9
m *= 10
ans += n//m
print(ans)
main()
- Time Complexity of each test case = O(log(n, base=10))
- Space Complexity of each test case = O(1)
- Time Complexity = O(t*log(n, base=10))
- Space Complexity = O(1)
Follow for more.