Given two positive integers L, R and a digit D, find out all the good numbers in the range [L, R], which do not contain the digit D.
A number is a good number if it's every digit is larger than the sum of digits which are on the right side of that digit. 
9620  is good as (2 > 0, 6 > 2+0, 9 > 6+2+0)
Example 1:
Input:
L=200
R=700
D=4
Output:
{210, 310, 320, 510, 520, 521, 530, 531,
610, 620, 621, 630, 631, 632, 650}
Explanation:
These are the only good numbers in the range
[200,700]
Example 2:
Input:
L=100
R=500
D=5
Output:
{210, 310, 320, 410, 420, 421, 430}
Explanation:
These are the only good numbers in the range
[100,500]
Your Task:
You don't need to read input or print anything. Your task is to complete the function goodNumbers() which takes 3 integers L, R, and D as input parameters and returns all the good numbers in the range [L, R]. (Returns empty if there are no good numbers in that range)
Expected Time Complexity:O(N)
Expected Auxillary Space:O(1)
Constraints:
1<=L<=R<=10^{6}
0<=D<10

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def goodNumbers(self,L,R,D):

        #code here



Solutions:
class Solution:

	def goodNumbers(self, L, R, D):
		ans = []
		for el in range(L, R + 1):
			par_el = el
			cnt = 0
			if D == 0 and par_el == 0:
				continue
			boo = True
			first = False
			while par_el > 0:
				num = par_el % 10
				if num == D or par_el == D or par_el <= cnt:
					if par_el != 0:
						boo = False
					break
				par_el //= 10
				if num <= cnt and first:
					boo = False
					break
				cnt += num
				first = True
			if boo:
				ans.append(el)
		return ans


class Solution:

	def goodNumbers(self, L, R, D):
		numlist = []
		for no in range(L, R + 1):
			flag = 1
			sumOfDigits = 0
			result = 0
			i = no
			if i % 10 == 0 and D != 0:
				i = i / 10
			while i > 0:
				digit = i % 10
				if digit == D or digit <= sumOfDigits:
					flag = 0
					break
				result = result * 10 + digit
				sumOfDigits += digit
				i = i // 10
			if flag == 1:
				numlist.append(no)
		return numlist


class Solution:

	def goodNumbers(self, L, R, D):
		res = []
		i = L
		for i in range(L, R + 1):
			i = str(i)
			if str(D) in i:
				continue
			j = len(i) - 1
			sumj = 0
			while j > 0:
				sumj += int(i[j])
				if int(i[j - 1]) <= sumj:
					break
				j -= 1
			else:
				res.append(int(i))
		return res


class Solution:

	def isgood(self, number, sumright, D):
		if number == 0:
			return True
		digit = number % 10
		if digit <= sumright or digit == D:
			return False
		return self.isgood(number // 10, sumright + digit, D)

	def goodNumbers(self, L, R, D):
		res = []
		for i in range(L, R + 1):
			digit = i % 10
			if digit != D and self.isgood(i // 10, digit, D):
				res.append(i)
		return res


class Solution:

	def goodNumbers(self, L, R, D):

		def isGoodNumber(n: int, d):
			if n % 10 == d:
				return False
			s = n % 10
			n = n // 10
			while n > 0:
				remainder = n % 10
				n = n // 10
				if remainder == d:
					return False
				if remainder <= s:
					return False
				s += remainder
			return True
		ans = []
		for i in range(L, R + 1):
			if isGoodNumber(i, D):
				ans.append(i)
		return ans


class Solution:

	def good(self, n):
		cn = str(n)
		leng = len(cn)
		if leng == 1:
			return 1
		one = n // 10 ** (leng - 1)
		suma = 0
		for i in range(1, leng):
			if cn[i - 1] <= cn[i]:
				return 0
			suma += int(cn[i])
			if suma >= one:
				return 0
		return self.good(n % 10 ** (leng - 1))

	def goodNumbers(self, l, r, d):
		ans = []
		for i in range(l, r + 1):
			l = []
		for i in range(L, R + 1):
			t = i
			sum = 0
			while i != 0:
				r = i % 10
				if r == D:
					break
				sum += r
				a = i // 10
				if a != 0 and sum >= a % 10:
					break
				i = a
			if i == 0:
				l.append(t)
		return l


class Solution:

	def goodNumbers(self, L, R, D):
		op = []
		for i in range(L, R + 1):
			s = str(i)
			if str(D) in s:
				continue
			j = len(s) - 1
			s1 = 0
			while j > 0:
				s1 += int(s[j])
				if int(s[j - 1]) <= s1:
					break
				j -= 1
			else:
				op.append(i)
		return op

class Solution:

	def goodNumbers(self, L, R, D):
		op = []
		for i in range(L, R + 1):
			rem = 0
			s = 0
			j = i
			while i > 0:
				rem = i % 10
				if rem == D or ((s or j % 100 == 0) and rem <= s):
					break
				i //= 10
				s += rem
			else:
				op.append(j)
		return op


class Solution:

	def goodNumbers(self, L, R, D):

		def funk(r, d):
			s = 0
			l = 10
			p = r
			while p != 0:
				k = p % 10
				if k == d:
					return False
				s += k
				p //= 10
				if p != 0 and s >= p % 10:
					return False
			return True
		ans = []
		for r in range(L, R + 1):
			if funk(r, D):
				ans += [r]
		return ans


class Solution:

	def goodNumbers(self, L, R, d):

		def isValid(n, d, sum):
			if n == 0:
				return True
			digit = n % 10
			if digit == d:
				return False
			if digit <= sum:
				return False
			return isValid(n // 10, d, sum + digit)
		ans = []
		for i in range(L, R + 1):
			if i % 10 == 0:
				if d != 0:
					i = i // 10
					if isValid(i, d, 0):
						ans += (i * 10,)
				else:
					continue
			elif isValid(i, d, 0):
				ans += (i,)
		return ans


class Solution:

	def goodNumbers(self, L, R, D):
		l = []
		for i in range(L, R + 1):
			valid = 1
			n = i
			s = 0
			k = 0
			while n != 0:
				rem = n % 10
				if rem == D:
					valid = 0
					break
				if k == 0:
					if rem >= s:
						valid = 1
					else:
						valid = 0
						break
				elif rem > s:
					valid = 1
				else:
					valid = 0
					break
				s = s + rem
				n = n // 10
				k = k + 1
			if valid == 1:
				l.append(i)
		return l


class Solution:

	def goodNumbers(self, L, R, D):
		l = []
		for i in range(L, R + 1):
			t = i
			sum = 0
			while i != 0:
				r = i % 10
				if r == D:
					break
				sum += r
				a = i // 10
				if a != 0 and sum >= a % 10:
					break
				i = a
			if i == 0:
				l.append(t)
		return l


class Solution:

	def isValid(self, N, D):
		dig = N % 10
		sum = dig
		if dig == D:
			return False
		N //= 10
		while N > 0:
			dig = N % 10
			if dig == D or dig <= sum:
				return False
			sum += dig
			N //= 10
		return True

	def goodNumbers(self, L, R, D):
		ans = []
		for i in range(L, R + 1):
			if ob.isValid(i, D) == True:
				ans.append(i)
		return ans


class Solution:

	def goodNumbers(self, L, R, D):
		ans = []

		def isValid(num, D):
			dig = num % 10
			if dig == D:
				return False
			sumtillnow = dig
			num = num // 10
			while num > 0:
				dig = num % 10
				if dig == D or dig <= sumtillnow:
					return False
				sumtillnow += dig
				num = num // 10
			return True
		for num in range(L, R + 1):
			if isValid(num, D):
				ans.append(num)
		return ans


class Solution:

	def goodNumbers(self, L, R, D):

		def valid(temp, s, D):
			if temp == 0:
				return True
			rem = temp % 10
			if rem == D:
				return False
			elif rem <= s:
				return False
			if s == -1:
				s = rem
			else:
				s += rem
			temp = temp // 10
			return valid(temp, s, D)
		res = []
		for i in range(L, R + 1):
			if valid(i, -1, D):
				res.append(i)
		return res


class Solution:

	def isGoodNumber(self, n, D, sum):
		if n == 0:
			return True
		x = n % 10
		if x == D or x <= sum:
			return False
		n = n // 10
		if sum == -1:
			sum = x
		else:
			sum += x
		return self.isGoodNumber(n, D, sum)

	def goodNumbers(self, L, R, D):
		ans = []
		for i in range(L, R + 1):
			if self.isGoodNumber(i, D, -1):
				ans.append(i)
		return ans


class Solution:

	def goodNumbers(self, L, R, D):

		def check(i, D):
			s = 0
			dig = i
			while i > 0:
				dig = i % 10
				if dig == D:
					break
				s += dig
				a = i // 10
				if a != 0 and s >= a % 10:
					break
				i = a
			if i == 0:
				return True
			return False
		result = []
		for i in range(L, R + 1):
			if check(i, D):
				result.append(i)
		return result


class Solution:

	def goodNumbers(self, L, R, D):

		def check(num, cursum):
			if num == 0:
				return True
			if num % 10 <= cursum or num % 10 == D:
				return False
			return check(num // 10, cursum + num % 10 + (cursum == -1))
		ans = []
		for i in range(L, R + 1):
			if check(i, -1):
				ans.append(i)
		return ans


class Solution:

	def valid(self, L, D):
		if L % 10 == D:
			return False
		sum = L % 10
		n = int(L / 10)
		while n > 0:
			digit = n % 10
			if digit == D or sum >= digit:
				return False
			else:
				sum += digit
				n = int(n / 10)
		return True

	def goodNumbers(self, L, R, D):
		list = []
		for num in range(L, R + 1):
			ans = self.valid(num, D)
			if ans:
				list.append(num)
		return list


from math import ceil, floor

class Solution:

	def goodNumbers(self, L, R, D):
		l = []
		for i in range(L, R + 1):
			t = i
			sum = 0
			while i != 0:
				r = i % 10
				if r == D:
					break
				sum += r
				a = i // 10
				if a != 0 and sum >= a % 10:
					break
				i = a
			if i == 0:
				l.append(t)
		return l


class Solution:

	def goodNumbers(self, L, R, D):
		ans = []
		for i in range(L, R + 1):
			temp = i
			b = True
			s = temp % 10
			if s == D:
				continue
			temp //= 10
			while temp > 0:
				check = temp % 10
				if s >= check or check == D:
					b = False
					break
				s += temp % 10
				temp //= 10
			if b:
				ans.append(i)
		return ans


class Solution:

	def isGood(self, L, D):
		sum = L % 10
		if sum == D:
			return False
		L = L // 10
		while L:
			digit = L % 10
			if digit == D or sum >= digit:
				return False
			L = L // 10
			sum += digit
		return True

	def goodNumbers(self, L, R, D):
		res = []
		while L != R + 1:
			if self.isGood(L, D):
				res.append(L)
			L += 1
		return res


def good(n, d, sum):
	if n == 0:
		return True
	if n % 10 == d:
		return False
	if n % 10 <= sum:
		return False
	sum += n % 10
	return good(n // 10, d, sum)

class Solution:

	def goodNumbers(self, L, R, D):
		l = []
		for i in range(L, R + 1):
			sum = 0
			zero = 0
			if i % 10 == 0 and D != 0:
				zero = 1
				i = i // 10
			if good(i, D, sum):
				if zero == 1:
					i *= 10
				l.append(i)
		return l


class Solution:

	def isGoodNumber(self, n, d, summ):
		if n == 0:
			return True
		r = n % 10
		if r == d or summ >= r:
			return False
		n = n // 10
		if summ == -1:
			summ = r
		else:
			summ += r
		return self.isGoodNumber(n, d, summ)

	def goodNumbers(self, L, R, D):
		l = []
		for i in range(L, R + 1):
			temp = self.isGoodNumber(i, D, -1)
			if temp:
				l.append(i)
		return l


class Solution:

	def goodNumbers(self, L, R, D):
		l = []
		for i in range(L, R + 1):
			temp = i
			summ = i % 10
			if summ == D:
				continue
			i = i // 10
			while i != 0:
				r = i % 10
				if r <= summ or r == D:
					break
				summ = summ + r
				i = i // 10
			if i == 0:
				l.append(temp)
		return l


class Solution:

	def goodNumbers(self, l, r, d):

		def isValid(n, d):
			digit = n % 10
			sum = digit
			if digit == d:
				return False
			n = int(n / 10)
			while n > 0:
				digit = n % 10
				if digit == d or digit <= sum:
					return False
				else:
					sum += digit
					n = int(n / 10)
			return True
		ans = []
		for i in range(L, R + 1):
			if isValid(i, d):
				ans.append(i)
		return ans

		def fun(l, d, pre=0):
			if l <= 0:
				return True
			rem = l % 10
			if rem == d:
				return False
			pre += rem
			l = l // 10
			if pre <= rem:
				fun(l, d, pre)
		ans = []
		for x in range(l, r):
			temp = fun(x, d)
			if temp:
				ans.append(x)
		return ans


class Solution:

	def goodNumbers(self, L, R, D):
		D = str(D)
		good_numbers = list()
		for num in range(L, R + 1):
			str_num = str(num)
			if D not in str_num and self.good_number(str_num):
				good_numbers.append(num)
		return good_numbers

	def good_number(self, str_num: str) -> bool:
		end = -1 * len(str_num) - 1
		curr_sum = int(str_num[-1])
		for idx in range(-2, end, -1):
			if int(str_num[idx]) <= curr_sum:
				return False
			curr_sum += int(str_num[idx])
		return True


class Solution:

	def goodNumbers(self, L, R, D):

		def good(x):
			x = str(x)
			res = int(x[-1])
			i = len(x) - 2
			while i >= 0:
				if int(x[i]) > res:
					res += int(x[i])
					i -= 1
				else:
					return False
			return True
		l = []
		for i in range(L, R + 1):
			i = str(i)
			if str(D) not in i:
				if good(i):
					l.append(i)
		return l


def isValid(num, D):
	s = num % 10
	if s == D:
		return False
	n = num // 10
	while n > 0:
		d = n % 10
		if d == D:
			return False
		if d > s:
			s = s + d
			n = n // 10
		else:
			return False
	return True

class Solution:

	def goodNumbers(self, L, R, D):
		ans = []
		for i in range(L, R + 1):
			if isValid(i, D):
				ans.append(i)
		return ans


class Solution:

	def func(self, N, D, s):
		if s == -1:
			if N % 10 == D:
				return False
			return self.func(N // 10, D, N % 10)
		if N == 0:
			return True
		dig = N % 10
		if dig <= s or dig == D:
			return False
		return self.func(N // 10, D, s + dig)

	def checkGoodNumber(self, N, D):
		return self.func(N, D, -1)

	def goodNumbers(self, L, R, D):
		res = []
		for i in range(L, R + 1):
			if self.checkGoodNumber(i, D):
				res.append(i)
		return res


class Solution:

	def goodNumbers(self, l, r, d):
		ans = []
		for i in range(l, r + 1):
			if self.isvalid(i, d) == True:
				ans.append(i)
		return ans

	def isvalid(self, n, d):
		dig = n % 10
		sum = dig
		if dig == d:
			return False
		n = n // 10
		while n > 0:
			dig = n % 10
			if dig == d or dig <= sum:
				return False
			n = n // 10
			sum += dig
		return True


class Solution:

	def isValid(self, n, d):
		digit = n % 10
		if digit == d:
			return False
		sum1 = digit
		n = n // 10
		while n > 0:
			digit = n % 10
			if digit == d or digit <= sum1:
				return False
			else:
				sum1 += digit
				n = n // 10
		return True

	def goodNumbers(self, L, R, d):
		res = []
		for i in range(L, R + 1):
			if self.isValid(i, d):
				res.append(i)
		return res


class Solution:

	def good(self, n, D):
		d = n % 10
		left_sum = d
		if d == D:
			return False
		n //= 10
		while n:
			d = n % 10
			if d == D or d <= left_sum:
				return False
			else:
				left_sum += d
				n //= 10
		return True

	def goodNumbers(self, L, R, D):
		all_good = []
		for i in range(L, R + 1):
			if self.good(i, D):
				all_good.append(i)
		return all_good


class Solution:

	def goodNumbers(self, L, R, D):
		res = []
		for i in range(L, R + 1):
			if i % 10 != D and self.check(i // 10, D, i % 10):
				res.append(i)
		return res

	def check(self, n, d, s):
		if n == 0:
			return True
		if n % 10 <= s or n % 10 == d:
			return False
		s += n % 10
		if not self.check(n // 10, d, s):
			return False
		return True


class Solution:

	def isvalid(self, n, d):
		digit = n % 10
		sum = digit
		if digit == d:
			return False
		n = int(n / 10)
		while n > 0:
			digit = n % 10
			if digit == d or digit <= sum:
				return False
			else:
				sum += digit
				n = n // 10
		return True

	def goodNumbers(self, L, R, D):
		res = []
		for i in range(L, R + 1):
			if self.isvalid(i, D):
				res.append(i)
		return res


class Solution:

	def isValid(self, n, d):
		digit = n % 10
		s = digit
		if digit == d:
			return False
		n = int(n / 10)
		while n > 0:
			digit = n % 10
			if digit == d or digit <= s:
				return False
			else:
				s += digit
				n = int(n / 10)
		return True

	def goodNumbers(self, L, R, d):
		l = []
		for i in range(L, R + 1):
			if self.isValid(i, d):
				l.append(i)
		return l


def isValid(number, d):
	digit = number % 10
	sum = digit
	if digit == d:
		return False
	number = int(number / 10)
	while number:
		digit = number % 10
		if digit == d or digit <= sum:
			return False
		else:
			sum = sum + digit
			number = int(number / 10)
	return True

class Solution:

	def goodNumbers(self, L, R, D):
		rtrn = []
		for i in range(L, R + 1):
			if isValid(i, D):
				rtrn = rtrn + [i]
		return rtrn


class Solution:

	def goodNumbers(self, L, R, D):
		result = []

		def check(num, sum_):
			if num <= 0:
				return True
			if num % 10 <= sum_[0] or num % 10 == D:
				return False
			sum_[0] += num % 10
			return check(num // 10, sum_)
		for number in range(L, R + 1):
			sum_ = [number % 10]
			if sum_[0] == D:
				continue
			if check(number // 10, sum_):
				result.append(number)
		return result


def isGood(n, D):
	d = n % 10
	if d == D:
		return False
	n //= 10
	s = d
	while n:
		d = n % 10
		if d == D or d <= s:
			return False
		s += d
		n //= 10
	return True

class Solution:

	def goodNumbers(self, L, R, D):
		ret = []
		for i in range(L, R + 1):
			if isGood(i, D):
				ret.append(i)
		return ret


class Solution:

	def goodNumbers(self, L, R, D):
		ans = []
		c = 0
		for i in range(L, R + 1):
			s = i % 10
			if s == D:
				continue
			if self.boolCheck(i // 10, D, s):
				ans.append(i)
		return ans

	def boolCheck(self, n, d, s):
		if n <= 0:
			return True
		if n % 10 <= s or n % 10 == d:
			return False
		s += n % 10
		if self.boolCheck(n // 10, d, s) == False:
			return False
		return True


class Solution:

	def isGood(self, no, a, D):
		if no % 10 <= a or no % 10 == D:
			return False
		if no < 10 and a < no:
			return True
		return self.isGood(no // 10, a + no % 10, D)

	def goodNumbers(self, L, R, D):
		ans = []
		for i in range(L, R + 1):
			if i % 10 == D:
				continue
			if i < 10:
				ans.append(i)
				continue
			if self.isGood(i // 10, i % 10, D):
				ans.append(i)
		return ans


class Solution:

	def isValid(self, n, D):
		if n % 10 == D:
			return False
		sum = n % 10
		n //= 10
		while n > 0:
			d = n % 10
			if d <= sum or d == D:
				return False
			else:
				sum += d
			n //= 10
		return True

	def goodNumbers(self, L, R, D):
		out = []
		for num in range(L, R + 1):
			if self.isValid(num, D):
				out.append(num)
		return out


class Solution:

	def goodNumbers(self, L, R, D):

		def isvalid(n, d):
			last = n % 10
			sum = last
			if last == d:
				return 0
			n = n // 10
			while n:
				dig = n % 10
				if dig == d or dig <= sum:
					return 0
				else:
					sum += dig
					n = n // 10
			return 1
		res = []
		for i in range(L, R + 1):
			if isvalid(i, D):
				res.append(i)
		return res


class Solution:

	def goodNumbers(self, L, R, D):
		res = []

		def is_good(num):
			digit = num % 10
			cur_sum = digit
			if digit == D:
				return False
			num = int(num / 10)
			while num > 0:
				digit = num % 10
				if digit == D or digit <= cur_sum:
					return False
				else:
					cur_sum += digit
					num = int(num / 10)
			return True
		for num in range(L, R + 1):
			if is_good(num):
				res.append(num)
		return res


class Solution:

	def goodNumbers(self, L, R, D):
		ans = []
		for i in range(L, R + 1):
			num = i
			sums = -1
			flag = False
			while num > 0:
				rem = num % 10
				if rem == D:
					flag = True
					break
				elif rem <= sums:
					flag = True
					break
				elif sums == -1:
					sums = rem
				else:
					sums += rem
				num = num // 10
			if not flag:
				ans.append(i)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, R, D) = map(int, input().strip().split())
		ob = Solution()
		ans = ob.goodNumbers(L, R, D)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def test(digit, D):
		sum = digit % 10
		if digit % 10 == D:
			return False
		digit = digit // 10
		while digit > 0:
			lst_digit = digit % 10
			if lst_digit == D or lst_digit <= sum:
				return False
			sum += lst_digit
			digit = digit // 10
		return True

	def goodNumbers(self, L, R, D):
		ans = []
		for i in range(L, R + 1):
			if Solution.test(i, D):
				ans.append(i)
		return ans