Given a positive value N, we need to find the count of numbers smaller than or equal to N such that the difference between the number and sum of its digits is greater than or equal to the given specific value K.
Example 1:
Input:N = 13, K = 2
Output: 4
Explanation: 
10, 11, 12 and 13 satisfy the given condition shown below, 
10 - sumofdigit(10) = 9 >= 2
11 - sumofdigit(11) = 9 >= 2
12 - sumofdigit(12) = 9 >= 2
13 - sumofdigit(13) = 9 >= 2 
Example 2:
Input: N = 10, K = 5
Output: 1
Explanation: 
Only 10 satisfies the givencondition as 
10 - sumofdigit(10) = 9 >= 5
Your Task:
You don't need to read input or print anything. Your task is to complete the function numberCount()which takes an integer N and an integer K as inputs and returns the count of numbers less than or equal to N such that the difference between the number and its sum of digits is greater than K.
Expected Time Complexity: Log(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N, K<= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Mathematics

Complete search

Starter code: #User function Template for python3



class Solution:

    def numberCount(self,n,k):

    # code here



Solutions:
class Solution:

	def numberCount(self, n, k):
		(left, right) = (1, n + 1)
		while left <= right:
			mid = (left + right) // 2
			if self.f1(mid) < k:
				left = mid + 1
			else:
				right = mid - 1
		if n - left + 1 <= 0:
			return 0
		return n - left + 1

	def f1(self, mid):
		temp = mid
		s = 0
		while mid > 0:
			s += mid % 10
			mid //= 10
		return temp - s


def sod(x):
	s = 0
	while x != 0:
		s = s + x % 10
		x = x // 10
	return s

class Solution:

	def numberCount(self, n, k):
		if n < 100000:
			c = 0
			l = 0
			h = n
			while l <= h:
				mid = l + (h - l) // 2
				t = sod(mid)
				if mid - t < k:
					l = mid + 1
				else:
					h = mid - 1
			return n - h
		return 0


class Solution:

	def numberCount(self, n, k):
		j = n

		def sumofdigits(n):
			summ = 0
			while n > 0:
				r = n % 10
				n = n // 10
				summ += r
			return summ
		s = 0
		e = n
		out = 0
		while s <= e:
			mid = (s + e) // 2
			if mid - sumofdigits(mid) >= k:
				out = max(out, j - mid + 1)
				e = mid - 1
			else:
				s = mid + 1
		return out


class Solution:

	def digit_sum_diff(self, n):
		digit_sum = 0
		while n:
			digit_sum += n % 10
			n //= 10
		return digit_sum

	def numberCount(self, n, k):
		if n < 10:
			return 0
		p = 10
		if n - self.digit_sum_diff(n) < k:
			return 0
		while p < n:
			if p - self.digit_sum_diff(p) < k:
				p += 10
			else:
				break
		if n - p + 1 < 0:
			return 0
		else:
			return n - p + 1


def mgc(s):
	ans = 0
	temp = s
	while s > 0:
		ans += s % 10
		s = s // 10
	return abs(ans - temp)

class Solution:

	def numberCount(self, n, k):
		(st, en) = (0, n)
		ans = 0
		while st <= en:
			mid = (st + en) // 2
			temp = mgc(mid)
			if temp >= k:
				ans = n - mid + 1
				en = mid - 1
			else:
				st = mid + 1
		return ans


class Solution:

	def predicate(self, num, k):
		s = 0
		for i in str(num):
			s += int(i)
		if num - s >= k:
			return 1
		return 0

	def numberCount(self, n, k):
		l = 1
		h = n
		while l <= h:
			mid = (l + h) // 2
			if self.predicate(mid, k):
				h = mid - 1
			else:
				l = mid + 1
		if mid == n and self.predicate(mid, k):
			return 1
		return n - h


class Solution:

	def numberCount(self, n, k):
		for i in range(10, n + 1, 10):
			if int(str(i)[0]) * 9 >= k:
				return n - i + 1
		return 0


class Solution:

	def numberCount(self, n, k):
		if not self.digitSum(n, k):
			return 0
		low = 0
		high = n
		num = n
		while low < high:
			num = (low + high) // 2
			if self.digitSum(num, k):
				high = num
			else:
				low = num + 1
		return n - high + 1

	def digitSum(self, n, target):
		num = str(n)
		summa = sum(map(int, list(num)))
		return n - summa >= target


class Solution:

	def numberCount(self, n, k):
		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 abs(mid - c) >= k:
				h = mid - 1
			else:
				l = mid + 1
		return n - h


class Solution:

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

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

	def numberCount(self, n, k):
		return n - self.binarysearch(0, n, k) + 1


class Solution:

	def numberCount(self, n, k):
		l = 0
		c = k // 9
		if k % 9 == 0:
			l = c * 10
		else:
			l = (c + 1) * 10
		if n - l + 1 > 0:
			return n - l + 1
		return 0


class Solution:

	def numberCount(self, n, k):
		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 < k:
				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 numberCount(self, n, k):
		ans = 0
		start = 1
		end = n
		while start <= end:
			mid = start + (end - start) // 2
			sum = self.sumOfDigits(mid)
			if mid - sum >= k:
				ans = n - mid + 1
				end = mid - 1
			else:
				start = mid + 1
		return ans


class Solution:

	def numberCount(self, n, k):
		low = k
		high = n
		count = 0
		while low <= high:
			mid = (low + high) // 2
			val = mid - self.digitSum(str(mid))
			if val >= k:
				count += high - mid + 1
				high = mid - 1
			else:
				low = mid + 1
		return count

	def digitSum(self, num):
		sum = 0
		for i in num:
			sum += int(i)
		return sum


class Solution:

	def numberCount(self, n, k):
		count = 0
		sum = 0
		for i in range(10, n + 1):
			num = i // 10
			m = i % 10
			sum = num + m
			if i - sum >= k:
				count += 1
		return count


class Solution:

	def calc(self, num):
		curSum = 0
		while num:
			curSum += num % 10
			num = num // 10
		return curSum

	def numberCount(self, n, k):
		if n < 10:
			return 0
		(start, end, res) = (10, n, -1)
		while start <= end:
			mid = (start + end) // 2
			digSum = self.calc(mid)
			temp = mid - digSum
			if temp >= k:
				res = mid
				end = mid - 1
			else:
				start = mid + 1
		return n - res + 1 if res != -1 else 0


def sumofdigit(x):
	Sum = 0
	while x != 0:
		Sum += x % 10
		x //= 10
	return Sum

class Solution:

	def numberCount(self, n, k):
		l = 1
		r = n
		c = 0
		while l <= r:
			mid = l + (r - l) // 2
			if mid - sumofdigit(mid) >= k:
				r = mid - 1
				c = r
			else:
				l = mid + 1
		if n - c == 0 | n - c == n:
			return 0
		return n - c


class Solution:

	def numberCount(self, n, k):
		j = 0
		l = 0
		count = 0
		sumofdigit = 0
		for i in range(n + 1):
			if j < l + 10:
				sumofdigit = j
				j += 1
			else:
				l += 1
				j = l + 1
				sumofdigit = l
			if i - sumofdigit >= k:
				count += 1
		return count


class Solution:

	def numberCount(self, n, k):

		def helper(num):
			temp = num
			suM = 0
			while temp != 0:
				suM += temp % 10
				temp = temp // 10
			return num - suM
		l = 1
		r = n
		ans = -1
		while l <= r:
			mid = (l + r) // 2
			if helper(mid) >= k:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return n - ans + 1 if ans != -1 else 0


class Solution:

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

	def isPossible(self, n: int, k: int) -> bool:
		if n - self.sumofDigits(n) >= k:
			return True
		return False

	def numberCount(self, n, k):
		(s, e) = (0, n)
		mid = s + (e - s) // 2
		ans = -1
		while s <= e:
			if self.isPossible(mid, k):
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
			mid = s + (e - s) // 2
		if ans == 0:
			return n - ans
		elif ans > 0:
			return n - ans + 1
		else:
			return 0


class Solution:

	def numberCount(self, n, k):
		l = 0
		r = n
		while l <= r:
			mid = (l + r) // 2
			z = mid
			sum = 0
			while z > 0:
				sum = sum + z % 10
				z = z // 10
			if abs(mid - sum) >= k:
				r = mid - 1
			else:
				l = mid + 1
		if abs(mid - sum) >= k:
			return n - mid + 1
		return n - mid


class Solution:

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

	def numberCount(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 numberCount(self, n, k):
		l = 0
		r = n
		while l <= r:
			add = 0
			mid = (l + r) // 2
			while mid > 0:
				add += mid % 10
				mid = mid // 10
			mid = (l + r) // 2
			if mid - add >= k:
				r = mid - 1
			else:
				l = mid + 1
		return n - r


class Solution:

	def find_digit_sum(self, n):
		ans = 0
		for i in str(n):
			ans += int(i)
		return n - ans

	def numberCount(self, n, k):
		low = 0
		high = n
		ans = 0
		while low <= high:
			mid = low + (high - low) // 2
			if self.find_digit_sum(mid) >= k:
				ans += high - mid + 1
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def is_valid(self, num, k):
		d_sum = 0
		tmp_num = num
		while num > 0:
			d_sum += num % 10
			num = num // 10
		return tmp_num - d_sum >= k

	def numberCount(self, n, k):
		left = 1
		right = n
		while left < right:
			mid = left + (right - left) // 2
			if self.is_valid(mid, k):
				right = mid
			else:
				left = mid + 1
		if self.is_valid(left, k):
			return n - left + 1
		return 0


class Solution:

	def numberCount(self, n, k):
		rem = n % 10
		digit = n - rem
		diff = digit - digit % 9
		while diff >= k:
			digit = digit - 10
			diff = digit - digit % 9
		ans = n - digit + 1 - 10
		if ans > 0:
			return ans
		return 0


class Solution:

	def numberCount(self, n, k):
		rem = n % 10
		d = n - rem
		di = d - d % 9
		while di >= k:
			d = d - 10
			di = d - d % 9
		ans = n - d + 1 - 10
		if ans > 0:
			return ans
		return 0


def check(n, k):
	a = n
	sm = 0
	while a:
		sm += a % 10
		a //= 10
	return n - sm >= k

class Solution:

	def numberCount(self, n, k):
		(s, e) = (1, n)
		cnt = 0
		while s <= e:
			m = (s + e) // 2
			if check(m, k):
				e = m - 1
				cnt = n - m + 1
			else:
				s = m + 1
		return cnt


class Solution:

	def numberCount(self, n, k):
		low = 0
		high = n
		while low <= high:
			mid = low + (high - low) // 2
			if self.Helper(mid, k):
				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 sumofint(self, val):
		finalsum = 0
		while val > 0:
			finalsum += val % 10
			val //= 10
		return finalsum

	def numberCount(self, n, k):
		if n < k:
			return 0
		elif n < 10:
			return 0
		low = 10
		high = n
		while low <= high:
			mid = (low + high) // 2
			if mid - self.sumofint(mid) >= k:
				high = mid - 1
			else:
				low = mid + 1
		return n - low + 1


class Solution:

	def numberCount(self, n, k):
		low = 1
		high = n
		while low <= high:
			mid = low + (high - low) // 2
			sum = self.calcSum(mid)
			if mid - sum < k:
				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 numberCount(self, n, k):
		result = 0
		diff = 0
		count = 0
		while k > diff:
			diff += 9
			count += 1
		if count * 10 <= n:
			result = n - count * 10 + 1
		return result