Given a number N, count the numbers from 1 to N which comprise of digits only from set {1, 2, 3, 4, 5}.
Example 1:
Input:
N = 20
Output: 10
Explanation: The numbers whose digits
are from the given set are:
1, 2, 3, 4, 5, 11, 12, 13, 14, 15.
Example 2:
Input:
N = 100
Output: 30
Your Task:
You don't need to read input or print anything. Your task is to complete the function countNumbers() which takes the integer n as input parameter and returns an integer denoting the answer.
Expected Time Complexity: O(N * number of digits in an integer)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N * number of digits in an integer)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def countNumbers(self, n):

        # code here

Solutions:
class Solution:

	def countNumbers(self, n):

		def isNums(n):
			while n > 0:
				rem = n % 10
				if rem == 0 or rem > 5:
					return False
				n = n // 10
			return True
		count = 0
		for i in range(1, n + 1):
			if isNums(i):
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		if n <= 5:
			return n
		elif n <= 10:
			return 5
		else:
			count = 0
			for i in range(1, n + 1):
				num = i
				flag = False
				while num > 0:
					rem = num % 10
					if rem >= 1 and rem <= 5:
						flag = True
					else:
						flag = False
						break
					num = num // 10
				if flag:
					count += 1
			return count


class Solution:

	def countNumbers(self, n):
		rule = '12345'
		count = 0
		for i in range(1, n + 1):
			for j in str(i):
				all = 0
				if j not in rule:
					break
				else:
					all += 1
			if all == len(str(j)):
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		k = '12345'
		c = 0
		for i in range(1, n + 1):
			s = str(i)
			if ('6' in s or '7' in s) or ('8' in s or '9' in s) or '0' in s:
				pass
			else:
				c = c + 1
		return c


class Solution:

	def countNumbers(self, n):
		number_digits = set(['1', '2', '3', '4', '5'])
		c = 0
		for i in range(1, n + 1):
			s = str(i)
			for digit in s:
				if digit not in number_digits:
					break
			else:
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		set1 = set(['1', '2', '3', '4', '5'])
		ans = 0
		if n <= 10:
			return 5
		else:
			for i in range(1, n + 1):
				f = 0
				while i > 0:
					rem = i % 10
					if rem >= 1 and rem <= 5:
						f = 1
					else:
						f = 0
						break
					i //= 10
				if f:
					ans += 1
		return ans


class Solution:

	def countNumbers(self, n):
		reference = set('12345')
		count = 0
		for index in range(1, n + 1, 10):
			num = str(index)
			count += 5 if len(set(num).difference(reference)) == 0 else 0
		last = int(str(n)[-1])
		count -= 5 - last if len(set(str(n)).difference(reference)) == 0 and 1 <= last <= 5 else 0
		return count


class Solution:

	def countNumbers(self, n):
		s = '12345'
		c = 0
		for i in range(1, n + 1):
			f = True
			for j in str(i):
				if j not in s:
					f = False
			if f:
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		digits = ['1', '2', '3', '4', '5']
		output = 0
		for num in range(1, n + 1):
			value = False
			for i in str(num):
				if i in digits:
					value = True
				else:
					value = False
					break
			if value == True:
				output += 1
		return output


class Solution:

	def countNumbers(self, n):
		c = 0
		for i in range(1, n + 1):
			while i:
				temp = i % 10
				if 1 <= temp <= 5:
					i //= 10
					continue
				else:
					break
			else:
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		if n <= 5:
			return n
		if n <= 10:
			return 5
		s = {1, 2, 3, 4, 5}
		count = 5
		for i in range(10, n + 1):
			num = i
			while num > 0:
				if num % 10 not in s:
					break
				else:
					num = num // 10
			if num == 0:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		arr_set = '12345'
		output = 0
		for i in range(1, n + 1):
			value = str(i)
			for item in value:
				if item not in arr_set:
					break
			else:
				output += 1
		return output


class Solution:

	def countNumbers(self, n):
		q = []
		count = 0
		for i in range(n + 1):
			zz = 0
			f = 0
			while i > 0:
				rem = i % 10
				i = i // 10
				f += 1
				if rem <= 5 and rem != 0:
					zz += 1
				else:
					break
			if zz == f and f != 0:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		s = {1, 2, 3, 4, 5}
		cnt = 0

		def check(num):
			while num:
				rem = num % 10
				num = num // 10
				if rem not in s:
					return False
			return True
		for i in range(1, n + 1):
			if check(i):
				cnt += 1
		return cnt


class Solution:

	def countNumbers(self, n):
		s = ['1', '2', '3', '4', '5']
		S = str(n)
		K = len(S)
		dp = [0] * K + [1]
		for i in range(K - 1, -1, -1):
			for d in s:
				if d < S[i]:
					dp[i] += len(s) ** (K - i - 1)
				elif d == S[i]:
					dp[i] += dp[i + 1]
		return dp[0] + sum((len(s) ** i for i in range(1, K)))


class Solution:

	def countNumbers(self, n):
		x = ['0', '6', '7', '8', '9']
		y = 0
		for i in range(1, n + 1):
			i = str(i)
			p = 0
			for j in x:
				if j in i:
					p += 1
					break
				else:
					pass
			if p == 0:
				y += 1
			else:
				p = 0
		return y


class Solution:

	def countNumbers(self, n):
		set1 = {1, 2, 3, 4, 5}
		ans = 0

		def check(num):
			while num:
				x = num % 10
				num = num // 10
				if x not in set1:
					return False
			return True
		for i in range(1, n + 1, 1):
			if check(i):
				ans += 1
		return ans


class Solution:

	def countNumbers(self, n):
		hashMap = set(['1', '2', '3', '4', '5'])
		tot = 0
		for i in range(1, n + 1):
			flag = 1
			for j in str(i):
				if j not in hashMap:
					flag = 0
					break
			if flag:
				tot += 1
		return tot


class Solution:

	def countNumbers(self, n):
		cnt = 0
		d = {1: 1, 2: 1, 3: 1, 4: 1, 5: 1}
		for i in range(1, n + 1):
			while i % 10 in d:
				i //= 10
			if i == 0:
				cnt += 1
		return cnt


class Solution:

	def countNumbers(self, n):
		count = 0
		for i in range(1, n + 1):
			i = str(i)
			if '6' in i or '7' in i or '8' in i or ('9' in i) or ('0' in i):
				count += 0
			else:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		s = set([6, 7, 8, 9, 0])
		res = []
		for i in range(1, n + 1):
			temp = i
			flag = True
			while i > 0:
				if i % 10 in s:
					flag = False
					break
				i = i // 10
			if flag:
				res.append(temp)
		return len(res)


class Solution:

	def countNumbers(self, n):
		count = 0
		for i in range(1, n + 1):
			flag = 1
			num = i
			while num != 0:
				rem = num % 10
				if rem != 1 and rem != 2 and (rem != 3) and (rem != 4) and (rem != 5):
					flag = 0
					break
				num = num // 10
			if flag == 1:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		count = 0
		setti = set('12345')
		for i in range(1, n + 1):
			add = 1
			for item in str(i):
				if item not in setti:
					add = 0
					break
			count += add
		return count


class Solution:

	def countNumbers(self, n):
		c = 0
		for i in range(1, n + 1):
			for x in str(i):
				if x not in '12345':
					break
			else:
				c += 1
		return c


class Solution:

	def countNumbers(self, n):

		def check(num):
			seti = {'1', '2', '3', '4', '5'}
			num = str(num)
			for j in num:
				if j not in seti:
					return False
			return True
		count = 0
		for i in range(1, n + 1):
			if check(i):
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		counter = 0
		for i in range(1, n + 1):
			num = int(i)
			flag = True
			while num > 0:
				if num % 10 == 0 or num % 10 > 5:
					flag = False
					break
				num = num // 10
			if flag:
				counter += 1
		return counter


class Solution:

	def countNumbers(self, n: int) -> int:
		digits = {1, 2, 3, 4, 5}
		count = 0
		for number in range(1, n + 1):
			while number:
				digit = number % 10
				if digit not in digits:
					break
				else:
					number //= 10
			else:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		if n <= 5:
			return n
		elif n <= 10:
			return 5
		else:
			c = 0
			for i in range(1, n + 1):
				no = i
				fl = False
				while no > 0:
					rm = no % 10
					if rm >= 1 and rm <= 5:
						fl = True
					else:
						fl = False
						break
					no = no // 10
				if fl:
					c += 1
			return c


class Solution:

	def countNumbers(self, n):
		count = 0
		for i in range(1, n + 1):
			flag = True
			for ch in str(i):
				if ch not in ['1', '2', '3', '4', '5']:
					flag = False
					break
			if flag:
				count = count + 1
		return count


class Solution:

	def digit(self, n):
		l = [1, 2, 3, 4, 5]
		while n:
			r = n % 10
			if r not in l:
				return False
			n //= 10
		return True

	def countNumbers(self, n):
		c = 0
		for i in range(1, n + 1):
			if self.digit(i):
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		count = 0
		s = {1, 2, 3, 4, 5}
		for i in range(1, n + 1):
			value = i
			while value:
				flag = 1
				digit = value % 10
				if digit not in s:
					flag = 0
					break
				value = value // 10
			if flag == 1:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		count = 0
		for i in range(1, n + 1):
			if self.check(i):
				count += 1
		return count

	def check(self, n):
		if n >= 1 and n <= 5:
			return True
		while n != 0:
			digit = n % 10
			if digit == 0 or digit > 5:
				return False
			n = n // 10
		return True


class Solution:

	def countNumbers(self, n):
		arr = [1, 2, 3, 4, 5]
		count = 0
		for i in range(n + 1):
			flag = False
			temp = i
			while temp > 0:
				if temp % 10 not in arr:
					flag = False
					break
				else:
					flag = True
				temp = temp // 10
			if flag == True:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		ans = 0
		check = '67890'
		while n >= 1:
			for ele in str(n):
				if ele in check:
					break
			else:
				ans += 1
			n -= 1
		return ans


class Solution:

	def countNumbers(self, n):
		c = 0
		flag = False
		for i in range(1, n + 1):
			nu = i
			while i != 0:
				r = i % 10
				if r >= 1 and r <= 5:
					flag = True
				else:
					flag = False
					break
				i = i // 10
			if flag:
				c = c + 1
		return c


class Solution:

	def countNumbers(self, n):
		c = n
		for i in range(1, n + 1):
			i = str(i)
			for j in i:
				if j not in '12345':
					c -= 1
					break
		return c


class Solution:

	def countNumbers(self, n):
		s = ['1', '2', '3', '4', '5']
		count = 0
		for i in range(1, n + 1):
			temp = True
			i = str(i)
			for j in i:
				if j not in s:
					temp = False
					break
			if temp:
				count += 1
		return count


class Solution:

	def countNumbers(self, n):
		c = 0
		a = ['0', '6', '7', '8', '9']
		for i in range(1, n + 1):
			for j in str(i):
				if j in a:
					break
			else:
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		lst = [1, 2, 3, 4, 5]
		c = 0
		for i in range(1, n + 1):
			while i > 0 and i % 10 in lst:
				i //= 10
			if i == 0:
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		ref = [1, 2, 3, 4, 5]
		count = 0
		for num in range(1, n + 1):
			s = num
			flag = 0
			while s > 0:
				dig = s % 10
				if dig not in ref:
					flag = 1
					break
				s = s // 10
			if flag == 0:
				count += 1
		return count
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		ob = Solution()
		ans = ob.countNumbers(n)
		print(ans)
		tc -= 1


class Solution:

	def countNumbers(self, n):
		c = 0
		k = 0
		for i in range(1, n + 1):
			m = i
			while m != 0:
				x = m % 10
				if x == 1 or x == 2 or x == 3 or (x == 4) or (x == 5):
					k = k + 1
				else:
					k = 0
					break
				m = m // 10
			if k != 0:
				c = c + 1
		return c
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		ob = Solution()
		ans = ob.countNumbers(n)
		print(ans)
		tc -= 1


class Solution:

	def countNumbers(self, n):
		arr = ['1', '2', '3', '4', '5']
		count = 0
		flag = 0
		for i in range(1, n + 1):
			s = str(i)
			for y in s:
				if y not in arr:
					flag = 1
					break
				else:
					flag = 0
			if flag == 0:
				count += 1
		return count
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		ob = Solution()
		ans = ob.countNumbers(n)
		print(ans)
		tc -= 1


class Solution:

	def countNumbers(self, n):
		s = 0
		for i in range(1, n + 1):
			k = str(i)
			c = 1
			for j in k:
				if j not in '12345':
					c = 0
					break
			if c:
				s += 1
		return s
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		ob = Solution()
		ans = ob.countNumbers(n)
		print(ans)
		tc -= 1


class Solution:

	def countNumbers(self, n):
		count = 0
		counter = 0
		for i in range(1, n + 1):
			num = i
			while num != 0:
				if num % 10 < 6 and num % 10 > 0:
					counter = 1
				else:
					counter = 0
					break
				num = num // 10
			count = count + counter
		return count
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		ob = Solution()
		ans = ob.countNumbers(n)
		print(ans)
		tc -= 1


class Solution:

	def countNumbers(self, n):
		if n <= 5:
			return n
		l = [1, 2, 3, 4, 5]
		c = 5
		while True:
			b = []
			for i in l:
				b.append(i * 10 + 1)
				b.append(i * 10 + 2)
				b.append(i * 10 + 3)
				b.append(i * 10 + 4)
				b.append(i * 10 + 5)
			f = 0
			for i in b:
				if i <= n:
					c += 1
				else:
					f = 1
					break
			if f == 1:
				break
			l = b
		return c
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		ob = Solution()
		ans = ob.countNumbers(n)
		print(ans)
		tc -= 1


class Solution:

	def countNumbers(self, n):
		count = 0
		for i in range(1, n + 1):
			s = 1
			for d in str(i):
				if d not in '12345':
					s = 0
					break
			if s:
				count = count + 1
		return count


class Solution:

	def countNumbers(self, n):
		l = [1, 2, 3, 4, 5]
		c = 0
		for i in range(1, n + 1):
			k = i
			m = 1
			while k != 0:
				rem = k % 10
				if rem in l:
					m = 1
				else:
					m = 0
					break
				k = k // 10
			if m == 1:
				c = c + 1
		return c


class Solution:

	def countNumbers(self, n):
		l = [1, 2, 3, 4, 5]
		ans = 0
		for cur in range(1, n + 1):
			while cur > 0 and cur % 10 in l:
				cur //= 10
			if cur == 0:
				ans += 1
		return ans


class Solution:

	def countNumbers(self, n):
		num = n
		for i in range(1, n + 1):
			j = i
			f = 0
			while j > 0:
				r = j % 10
				j = j // 10
				if r > 5 or r < 1:
					f = 1
					break
			if f == 1:
				num = num - 1
		return num


class Solution:

	def countNumbers(self, n):
		x = (1, 2, 3, 4, 5)
		c = 0
		for i in range(1, n + 1):
			j = i
			flag = True
			while j != 0:
				if j % 10 in x:
					j = j // 10
				else:
					flag = False
					break
			if flag == True:
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		s = set([1, 2, 3, 4, 5])
		ans = 0
		for i in range(1, n + 1):
			while i > 0:
				x = i % 10
				if x not in s:
					break
				i = i // 10
			else:
				ans += 1
		return ans


class Solution:

	def countNumbers(self, n):
		counter = 0
		for i in range(0, n + 1):
			flag = 1
			for char in str(i):
				if char not in '12345':
					flag = 0
					break
			if flag:
				counter += 1
		return counter


class Solution:

	def countNumbers(self, n):
		c = 0
		s1 = {1, 2, 3, 4, 5}
		for i in range(1, n + 1):
			s = str(i)
			if '6' not in s and '7' not in s and ('8' not in s) and ('9' not in s) and ('0' not in s):
				c += 1
		return c


class Solution:

	def countNumbers(self, n):
		s = {1, 2, 3, 4, 5}
		count = 0
		for i in range(1, n + 1):
			all_present = True
			if i // 10 <= 0:
				if i in s:
					count += 1
			else:
				while i > 0:
					num = i % 10
					if num in s:
						pass
					else:
						all_present = False
						break
					i = i // 10
				if all_present == True:
					count += 1
		return count


class Solution:

	def countNumbers(self, n):
		s = ['1', '2', '3', '4', '5']
		cnt = 0
		for i in range(1, n + 1):
			p = str(i)
			for j in p:
				if j not in s:
					cnt += 1
					break
		return n - cnt


class Solution:

	def countNumbers(self, n):
		ans = 0
		for i in range(1, n + 1):
			s = str(i)
			f = 1
			for j in s:
				if j != '1' and j != '2' and (j != '3') and (j != '4') and (j != '5'):
					f = 0
					break
			if f == 1:
				ans = ans + 1
		return ans


class Solution:

	def ifthere(self, n):
		while n > 0:
			x = n % 10
			if x == 0 or x > 5:
				return 0
			n = n // 10
		return 1

	def countNumbers(self, n):
		ob = Solution()
		count = 0
		for i in range(n + 1):
			if i > 0:
				if ob.ifthere(i):
					count += 1
		return count


class Solution:

	def countNumbers(self, n):
		count = 0
		for i in range(n + 1):
			flag = 1
			for j in str(i):
				if j not in '12345':
					flag = 0
					break
			if flag:
				count += 1
		return count