Two integers n and k is given. Find number of integers i from 1 to n such than difference of i and sum of digits of i is greater than k.
Examples:
Input : n=12 k=1 Output : 3 Explanation : 10,11,12 satisfies the given condition 10-sod(10) = 10-1 = 9 > k 11-sod(11) = 11-2 = 9 > k 12-sod(12) = 12-3 = 9 > k Input : n=25 k=20 Output : 0 Explanation : There is no integers in the given range satisfying the condition.
Approach :
For any integer x let say sod(x)= sum of digits of x f(x)=x-sod(x)
f(x) is increasing (not strictly) function.
So we can apply binary search to check the count of x from 1 to n satisfying the condition.
Below is the Python implementation of the above approach.
def sod(n):
# Function for calculating the sum of digits
g = list(str(n))
c = 0
for i in g:
c += int(i)
return c
def count_binary_search(n, k):
l = 0
r = n + 1
ans = n + 1 # Storing the answer
while r >= l:
# Calculating mid
mid = l + (r - l) // 2
# Checking the condition
if mid - sod(mid) > k:
# mid is the possible answer
ans = mid
r = mid - 1 # Integers lesser than mid are also possible
else:
l = mid + 1
print(n - ans + 1) # Numbers from ans to n satisfy the condition
n = 25
k = 20
count_binary_search(n, k)
n = 12
k = 1
count_binary_search(n, k)
Output:
0 3
Time Complexity: O(log(n))