Given an integer N. The task is to count the number of integers from 1 to N(inclusive) which contain 0’s as a digit.
Example 1:
Input: N = 21
Output: 2
Explanation: All numbers are 10,20.
Ã¢â¬â¹Example 2:
Input: N = 101
Output: 11
Explanation: All numbers are 10,20
30,40,50,60,70,80,90,100,101.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countZero() which takes N as inputs and returns the answer.
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def countZero (self, N):
        #complete the function here

Solutions:
class Solution:

	def zeroUpto(self, digits):
		first = int((10 ** digits - 1) // 9)
		second = int((9 ** digits - 1) // 8)
		return (first - second) * 9

	def countZero(self, N):
		sn = str(N)
		k = len(sn)
		nonzero = 0
		for i in range(k):
			if sn[i] == '0':
				nonzero -= 1
				break
			nonzero += (int(sn[i]) - 1) * 9 ** (k - 1 - i)
		no = 0
		remaining = 0
		count = 0
		for i in range(k):
			no = no * 10 + int(sn[i])
			if i != 0:
				count = count * 10 + 9
		remaining = no - count
		ans = self.zeroUpto(k - 1) + (remaining - nonzero - 1)
		return ans


import math

def get_digit(N, place):
	return int(N // 10 ** place % 10)

def get_digits(N, i, j):
	return int(N // 10 ** j % 10 ** (i - j + 1))

class Solution:

	def countZero(self, N):
		answer = 0
		length = int(math.log(N, 10)) + 1
		for place in range(length):
			digit = get_digit(N, place)
			if digit != 0 or place == 0:
				number = N // 10 ** (place + 1)
				answer += number * 9 ** place
			else:
				previous_digits = get_digits(N, length - 1, place + 1)
				step1 = (previous_digits - 1) * 9 ** place
				step2 = 0
				for current_place in range(place - 1, 0, -1):
					current_digit = get_digit(N, current_place)
					if current_digit == 0:
						break
					else:
						step2 += (current_digit - 1) * 9 ** current_place
				else:
					step2 += get_digit(N, 0)
				answer += step1 + step2
		return answer