Given a number N, count the numbers from 1 to N that don’t contain digit 3 in their decimal representation.
 
Example 1:
Input:
N = 5
Output:
4
Explanation:
From 1 - 5, only 3 contains
3 in its decimal representation
so output is 4
Example 2:
Input:
N = 25
Output:
22
Explanation:
In between 1 to 25,
3,13,23 contain 3 in their
decimal representaion so 
output is 25 - 3 = 22
Your Task:
You don't need to read input or print anything. Your task is to complete the function count() which takes an integer N as input parameter and returns an integer, the total count of numbers from 1 to N that don’t contain digit 3 in their decimal representation.
 
Expected Time Complexity: O(log N)
Expected Space Complexity: O(1)
 
Constraints:
0 <= N <= 500

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def count (self, N):
        # code here

Solutions:
class Solution:

	def count(self, N):
		ans = 0
		for i in range(1, N + 1):
			i = str(i)
			if '3' not in i:
				ans += 1
		return ans


class Solution:

	def count(self, N):
		ans = 0
		for x in range(1, N + 1):
			ans += '3' not in str(x)
		return ans


class Solution:

	def count(self, N):
		s = []
		i = 1
		while N != 0:
			if '3' not in str(i):
				s.append(i)
			i += 1
			N = N - 1
		return len(s)


class Solution:

	def count(self, N):
		c = 0
		for i in range(1, N + 1):
			if '3' in str(i):
				c += 1
		return N - c


class Solution:

	def count(self, N):
		ans = [i for i in range(1, N + 1) if '3' in str(i)]
		return N - len(ans)


class Solution:

	def count(self, N):
		a = []
		for i in range(1, N + 1):
			if '3' in str(i):
				a.append(i)
		return N - len(a)


class Solution:

	def count(self, N):
		l = []
		while N != 0:
			l.append(N % 10)
			N = N // 10
		k = -1
		for i in range(len(l)):
			if l[i] == 3:
				k = i
		for i in range(k):
			l[i] = 9
		for i in range(len(l)):
			if l[i] >= 3:
				l[i] -= 1
		s = 0
		for i in range(len(l) - 1, -1, -1):
			s = s * 10 + l[i]
		s = str(s)
		return int(s, 9)


class Solution:

	def count(self, N):
		count = 0
		for i in range(1, N + 1):
			if '3' not in str(i):
				count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.count(N))


class Solution:

	def count(self, n):
		if n < 3:
			return n
		elif n >= 3 and n < 10:
			return n - 1
		po = 1
		while n // po > 9:
			po *= 10
		msd = n // po
		if msd != 3:
			return self.count(msd) * self.count(po - 1) + self.count(msd) + self.count(n % po)
		return self.count(msd * po - 1)


class Solution:

	def count(self, N):
		c = 0
		for x in range(1, N + 1):
			if '3' not in str(x):
				c += 1
		return c


class Solution:

	def count(self, N):
		c = 0
		for i in range(1, N + 1):
			if i % 10 == 3 or i // 10 % 10 == 3 or i // 100 % 10 == 3:
				c += 1
		return N - c