Given a positive number N and a number D.  Find the count of positive numbers smaller or equal to  N such that the difference between the number and sum of its digits is greater than or equal to given specific value D.
Example 1:
Input:
N = 13 , D = 2
Output:
4
Explanation:
There are 4 numbers satisfying the
Conditions. These are 10,11,12 and 13.
Example 2:
Input:
N = 14 , D = 3
Output:
5
Explanation:
There are 5 numbers satisfying the
Conditions. These are 10,11,12,13 and 14.
Your Task:
You don't need to read input or print anything. Your task is to complete the function getCount() which takes 2 integers N and D as input and returns the answer.
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{16}
1<=D<=10^{15}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Mathematics

Starter code: #User function Template for python3



class Solution:

    def getCount(self, N , D):

        # code here 

Solutions:
class Solution:

	def getCount(self, N, D):
		if D == 0:
			return N

		def sumOfDigit(N):
			c = 0
			n = N
			while n != 0:
				c += n % 10
				n = n // 10
			return c
		low = 1
		high = N
		while low <= high:
			mid = int((low + high) / 2)
			if mid - sumOfDigit(mid) < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high


def getSumOfDigit(N):
	count = 0
	while N > 0:
		count += N % 10
		N //= 10
	return count

class Solution:

	def getCount(self, N, D):
		low = 1
		high = N
		n = None
		while low <= high:
			mid = (low + high) // 2
			if abs(mid - getSumOfDigit(mid)) >= D:
				if abs(mid - 1 - getSumOfDigit(mid - 1)) >= D:
					high = mid - 1
				else:
					n = mid
					break
			else:
				low = mid + 1
		if n != None:
			return N - n + 1
		else:
			return 0


class Solution:

	def getCount(self, N, D):
		low = 1
		high = N
		res = 0
		while low <= high:
			mid = low + (high - low) // 2
			num = mid
			sum_of_digits = 0
			while num:
				sum_of_digits += num % 10
				num = num // 10
			if mid - sum_of_digits >= D:
				res += 1
				high = mid - 1
			else:
				low = mid + 1
		return N - high


class Solution:

	def getCount(self, N, D):
		lower = 0
		upper = N
		while lower < upper:
			num = (lower + upper) // 2
			flag = self.diffGreater(num, D)
			if not flag and self.diffGreater(num + 1, D):
				return N - num
			if flag:
				upper = num
			else:
				lower = num + 1
		return 0

	def diffGreater(self, num, target):
		digits = sum(map(int, [*str(num)]))
		return num - digits >= target


class Solution:

	def getCount(self, N, D):
		l = 1
		h = N
		while l <= h:
			mid = (l + h) // 2
			c = 0
			while mid > 0:
				c += mid % 10
				mid = mid // 10
			mid = (l + h) // 2
			if mid - c < D:
				l = mid + 1
			else:
				h = mid - 1
		return N - h


class Solution:

	def getCount(self, n, d):

		def digsum(num):
			num = list(str(num))
			num = [int(i) for i in num]
			return sum(num)
		if n <= d:
			return 0
		l = 10
		r = n
		while l <= r:
			mid = (l + r) // 2
			if mid - digsum(mid) < d:
				l = mid + 1
			else:
				r = mid - 1
		return n - r


class Solution:

	def getCount(self, n, d):
		if d == 0:
			return n
		if n <= 9:
			return 0
		left = 10
		right = n
		res = 0
		while left <= right:
			mid = (left + right) // 2
			temp = mid - sum(list(map(int, str(mid))))
			if temp >= d:
				res = n - mid + 1
				right = mid - 1
			elif temp < d:
				left = mid + 1
		return res


class Solution:

	def digitsum(self, n):
		r = 0
		while n:
			(r, n) = (r + n % 10, n // 10)
		return r

	def getCount(self, N, D):
		(l, r) = (1, N)
		while l <= r:
			mid = (l + r) // 2
			count = self.digitsum(mid)
			if mid - count < D:
				l = mid + 1
			else:
				r = mid - 1
		return N - r


class Solution:

	def getCount(self, N, D):
		(l, r) = (1, N)
		while l <= r:
			mid = (l + r) // 2
			temp = 0
			while mid:
				temp += mid % 10
				mid //= 10
			mid = (l + r) // 2
			if mid - temp < D:
				l = mid + 1
			else:
				r = mid - 1
		return N - r


class Solution:

	def sumOfDigit(self, k):
		sod = 0
		while k:
			sod = sod + k % 10
			k = k // 10
		return sod

	def getCount(self, N, D):
		low = 1
		high = N
		while low <= high:
			mid = (low + high) // 2
			if mid - self.sumOfDigit(mid) < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high


class Solution:

	def dsum(self, n):
		sod = 0
		while n:
			sod += n % 10
			n = n // 10
		return sod

	def binarysearch(self, l, r, d):
		if l <= r:
			mid = (l + r) // 2
			if mid - self.dsum(mid) >= d:
				return self.binarysearch(l, mid - 1, d)
			else:
				return self.binarysearch(mid + 1, r, d)
		return l

	def getCount(self, N, D):
		return N - self.binarysearch(0, N, D) + 1


class Solution:

	def sud(self, n):
		s = 0
		while n > 0:
			s += n % 10
			n //= 10
		return s

	def getCount(self, N, d):
		(s, e) = (1, N)
		while s <= e:
			mid = s + (e - s) // 2
			su = self.sud(mid)
			if mid - su < d:
				s = mid + 1
			else:
				e = mid - 1
		return N - e


def sumofdigits(mid):
	count = 0
	while mid > 0:
		count += mid % 10
		mid = mid // 10
	return count

class Solution:

	def getCount(self, N, D):
		low = 1
		high = N
		while low <= high:
			mid = (low + high) // 2
			if mid - sumofdigits(mid) < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high


class Solution:

	def getCount(self, N, D):
		start = 1
		end = N
		while start <= end:
			mid = (start + end) // 2
			t = mid
			c = 0
			while t:
				c += t % 10
				t //= 10
			if mid - c < D:
				start = mid + 1
			else:
				end = mid - 1
		return N - end


class Solution:

	def sumOfDigits(self, number):
		sum = 0
		while number > 0:
			sum += number % 10
			number = number // 10
		return sum

	def getCount(self, N, D):
		ans = 0
		start = 1
		end = N
		while start <= end:
			mid = start + (end - start) // 2
			sum = self.sumOfDigits(mid)
			if mid - sum >= D:
				ans = N - mid + 1
				end = mid - 1
			else:
				start = mid + 1
		return ans


class Solution:

	def getCount(self, N, D):

		def digisum(num):
			xsum = 0
			while num:
				xsum += num % 10
				num = num // 10
			return xsum
		low = 1
		high = N
		while low <= high:
			mid = (low + high) // 2
			lo = mid - digisum(mid)
			if lo < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high


class Solution:

	def getCount(self, N, D):
		start = 1
		end = N
		temp = 0
		while start <= end:
			sum = 0
			mid = int((start + end) / 2)
			ele = mid
			while mid != 0:
				sum += mid % 10
				mid = int(mid / 10)
			if ele - sum < D:
				start = ele + 1
			else:
				end = ele - 1
		return N - end


class Solution:

	def dig_sum(self, H):
		s = str(H)
		c = 0
		for i in s:
			c += int(i)
		return c

	def getCount(self, N, D):
		if N <= D:
			return 0
		mid = D
		while mid - self.dig_sum(mid) < D:
			mid = mid + 1
		return N - mid + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, D) = map(int, input().split())
		ob = Solution()
		print(ob.getCount(N, D))


class Solution:

	def getCount(self, N, D):

		def sod(k):
			sumi = 0
			while k:
				sumi += k % 10
				k = k // 10
			return sumi
		(low, high) = (1, N)
		while low <= high:
			mid = (low + high) // 2
			if mid - sod(mid) < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, D) = map(int, input().split())
		ob = Solution()
		print(ob.getCount(N, D))


class Solution:

	def getCount(self, N, D):
		l = 1
		r = N
		while l <= r:
			mid = (l + r) // 2
			c = 0
			while mid > 0:
				c += mid % 10
				mid = mid // 10
			mid = (l + r) // 2
			if mid - c < D:
				l = mid + 1
			else:
				r = mid - 1
		return N - r
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, D) = map(int, input().split())
		ob = Solution()
		print(ob.getCount(N, D))


class Solution:

	def getCount(self, N, D):
		l = 1
		h = N
		while l <= h:
			m = (l + h) // 2
			x = 0
			while m > 0:
				x += m % 10
				m = m // 10
			m = (l + h) // 2
			if m - x < D:
				l = m + 1
			else:
				h = m - 1
		return N - h


class Solution:

	def getCount(self, N, D):

		def digitsum(i):
			s = 0
			k = str(i)
			for j in k:
				s = s + int(j)
			return s
		low = 0
		high = N
		while low <= high:
			mid = low + (high - low) // 2
			k = digitsum(mid)
			if mid - k < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high


class Solution:

	def sumOfDigit(self, K):
		sod = 0
		while K:
			sod = sod + K % 10
			K = K // 10
		return sod

	def getCount(self, n, diff):
		low = 1
		high = n
		while low <= high:
			mid = (low + high) // 2
			if mid - self.sumOfDigit(mid) < diff:
				low = mid + 1
			else:
				high = mid - 1
		return n - high


class Solution:

	def getCount(self, N, D):
		start = 0
		end = N
		cnt = 0
		while start <= end:
			mid = (start + end) // 2
			num = mid
			digits = 0
			while num > 0:
				di = num % 10
				digits += di
				num = num // 10
			if mid - digits < D:
				start = mid + 1
			else:
				end = mid - 1
		return N - end


class Solution:

	def calc_diff(self, num, D):
		str_num = str(num)
		digits_sum = 0
		for i in str_num:
			digits_sum += int(i)
		if num - digits_sum >= D:
			return True
		return False

	def getCount(self, N, D):
		ans = 0
		low = 0
		high = N
		while low <= high:
			mid = low + (high - low) // 2
			if self.calc_diff(mid, D):
				ans += high - mid + 1
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def sum_of_digit(self, n):
		res = 0
		while n:
			res += n % 10
			n //= 10
		return res

	def getCount(self, N, D):
		low = 1
		high = N
		while low <= high:
			mid = (low + high) // 2
			if mid - self.sum_of_digit(mid) < D:
				low = mid + 1
			else:
				high = mid - 1
		ans = N - high
		return ans


def sumd(n):
	return sum(map(int, list(str(n))))

def search(l, r, D):
	if r - l >= 1:
		mid = l + (r - l) // 2
		if mid - sumd(mid) < D:
			return search(mid + 1, r, D)
		else:
			return search(l, mid, D)
	if r - sumd(r) >= D:
		return r
	return -1

class Solution:

	def getCount(self, N, D):
		a = search(1, N, D)
		if a == -1:
			return 0
		return N - a + 1


def num_digit_sum(num):
	digit_sum = 0
	temp = num
	while temp != 0:
		digit_sum += temp % 10
		temp = temp // 10
	return num - digit_sum

class Solution:

	def getCount(self, n, d):
		minimum_num = float('inf')
		left_p = d
		right_p = n
		while left_p <= right_p:
			mid = (left_p + right_p) // 2
			if num_digit_sum(mid) >= d:
				if mid < minimum_num:
					minimum_num = mid
				right_p = mid - 1
			else:
				left_p = mid + 1
		if minimum_num == float('inf'):
			return 0
		total = n - minimum_num + 1
		return total


class Solution:

	def getCount(self, N, D):

		def binary_search(low, high, D):
			if low <= high:
				mid = (low + high) // 2
				num_1 = mid
				num_0 = mid - 1
				s_1 = 0
				while num_1 > 0:
					s_1 += num_1 % 10
					num_1 //= 10
				s_0 = 0
				while num_0 > 0:
					s_0 += num_0 % 10
					num_0 //= 10
				if mid - s_1 >= D and mid - 1 - s_0 < D:
					return mid
				elif mid - s_1 >= D:
					return binary_search(low, mid - 1, D)
				else:
					return binary_search(mid + 1, high, D)
			else:
				return 0
		if D == 0:
			return N
		elif D > 0 and N < 10:
			return 0
		elif D > N:
			return 0
		else:
			count = binary_search(1, N, D)
			return N - count + 1


class Solution:

	def getCount(self, N, D):
		ct = 0

		def SUM(num):
			temp = num
			digits = 0
			while temp > 0:
				rem = temp % 10
				quot = temp // 10
				digits += rem
				temp = quot
			return digits
		low = 1
		high = N
		while low <= high:
			mid = (low + high) // 2
			if mid - SUM(mid) < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high


class Solution:

	def getCount(self, N, D):
		i = 1
		j = N
		while i <= j:
			mid = (i + j) // 2
			sum = 0
			k = mid
			while k:
				sum += k % 10
				k = k // 10
			if mid - sum >= D:
				j = mid - 1
			else:
				i = mid + 1
		return N - j


class Solution:

	def getCount(self, N, D):
		low = 1
		high = N
		count = 0
		while low <= high:
			mid = low + (high - low) // 2
			sum = self.calcSum(mid)
			if mid - sum < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high

	def calcSum(self, mid):
		temp = mid
		ans = 0
		while temp > 0:
			num = temp % 10
			ans += num
			temp = temp // 10
		return ans


class Solution:

	def getCount(self, N, D):

		def getSum(N):
			sum = 0
			while N != 0:
				sum += N % 10
				N = N // 10
			return sum
		count = 0
		(lo, hi) = (0, N)
		while lo <= hi:
			mid = (lo + hi) // 2
			if mid - getSum(mid) >= D:
				hi = mid - 1
			else:
				lo = mid + 1
		return N - hi


class Solution:

	def getCount(self, N, D):
		low = 0
		high = N
		while low <= high:
			mid = low + (high - low) // 2
			if self.Helper(mid, D):
				high = mid - 1
			else:
				low = mid + 1
		return N - low + 1 if N >= low else 0

	def Helper(self, N, D):
		temp = N
		Sum = 0
		while temp > 0:
			Sum += temp % 10
			temp = temp // 10
		if N - Sum >= D:
			return True
		else:
			return False


class Solution:

	def condsatisfies(self, k):
		ct = 0
		mid = k
		while k > 0:
			ct += k % 10
			k //= 10
		return ct

	def getCount(self, N, D):
		if N < D:
			return 0
		low = 1
		high = N
		while low <= high:
			mid = (low + high) // 2
			if mid - self.condsatisfies(mid) >= D:
				high = mid - 1
			else:
				low = mid + 1
		return N - low + 1


class Solution:

	def getCount(self, N, D):
		low = 0
		high = N
		while low <= high:
			mid = (low + high) // 2
			s_d = 0
			m = mid
			while m > 0:
				rem = m % 10
				s_d += rem
				m = m // 10
			if mid - s_d < D:
				low = mid + 1
			else:
				high = mid - 1
		return N - high