Given a positive integer N. You have to find N^{th} natural number after removing all the numbers containing digit 9.
Example 1:
Input:
N = 8
Output:
8
Explanation:
After removing natural numbers which contains
digit 9, first 8 numbers are 1,2,3,4,5,6,7,8
and 8^{th} number is 8.
Example 2:
Input:
N = 9
Output:
10
Explanation:
After removing natural numbers which contains
digit 9, first 9 numbers are 1,2,3,4,5,6,7,8,10
and 9^{th} number is 10.
 
Your Task:
You don't need to read input or print anything. Complete the function findNth() which accepts an integer N as input parameter and return the N^{th} number after removing all the numbers containing digit 9.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{12}

Difficulty: MEDIUM_HARD
Tags: Mathematics
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

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

Solutions:
class Solution:

	def findNth(self, N):
		(res, P) = (0, 1)
		while N > 0:
			res += P * (N % 9)
			N = N // 9
			P *= 10
		return res


class Solution:

	def findNth(self, N):
		result = 0
		position = 1
		while N > 0:
			result += position * (N % 9)
			position *= 10
			N //= 9
		return result


class Solution:

	def findNth(self, N):
		l = []
		while N > 0:
			l.append(str(N % 9))
			N = N // 9
		S = ''.join(l)
		return int(S[::-1])


class Solution:

	def findNth(self, N):
		r = []
		while N > 0:
			r.insert(0, str(N % 9))
			N = N // 9
		return int(''.join(r))


class Solution:

	def findNth(self, N):
		c = 1
		ans = 0
		while N > 0:
			rem = N % 9
			ans += rem * c
			c = c * 10
			N = N // 9
		return ans


class Solution:

	def findNth(self, N):
		str1 = ''
		while N >= 9:
			str1 += str(N % 9)
			N //= 9
		str1 = str(N) + str1[::-1]
		return int(str1)


class Solution:

	def findNth(self, N):
		(a, b) = (0, 1)
		while N > 0:
			a = a + b * (N % 9)
			N = N // 9
			b = b * 10
		return a


class Solution:

	def findNth(self, N):
		a = []
		while N > 0:
			a.append(str(N % 9))
			N = N // 9
			s = ''.join(a)
		return int(s[::-1])


class Solution:

	def findNth(self, n):
		ans = 0
		temp = 1
		while n > 0:
			ans += temp * (n % 9)
			n = n // 9
			temp *= 10
		return ans


class Solution:

	def findNth(self, N):
		ans = ''
		while N > 0:
			r = N % 9
			ans += str(r)
			N = N // 9
		return ans[::-1]


class Solution:

	def findNth(self, N):
		r = 0
		p = 1
		while N > 0:
			r += p * (N % 9)
			N = N // 9
			p = p * 10
		return r


class Solution:

	def findNth(self, N):
		resArr = []
		while N:
			resArr.append(N % 9)
			N //= 9
		res = 0
		while resArr:
			res *= 10
			res += resArr.pop()
		return res


class Solution:

	def findNth(self, N):
		a = []
		while N:
			a.append(N % 9)
			N //= 9
		ans = 0
		for i in reversed(a):
			ans = ans * 10 + i
		return ans


class Solution:

	def findNth(self, N):
		a = []
		while N:
			a.append(N % 9)
			N //= 9
		ans = 0
		for i in range(len(a) - 1, -1, -1):
			ans = ans * 10 + a[i]
		return ans


class Solution:

	def findNth(self, N):
		n = N
		ans = 0
		p = 1
		while n > 0:
			ans += p * (n % 9)
			n //= 9
			p *= 10
		return ans


class Solution:

	def findNth(self, N, M: int=9):
		(alpha, beta) = (0, 1)
		while N > 0:
			alpha += beta * (int(N) % M)
			N /= M
			beta *= 10
		return alpha


class Solution:

	def findNth(self, N):
		res = []
		while N > 0:
			res.append(str(N % 9))
			N = N // 9
		return int(''.join(res)[::-1])


class Solution:

	def findNth(self, N):
		s = ''
		while N:
			s = str(N % 9) + s
			N = N // 9
		return int(s)


class Solution:

	def findNth(self, N):
		res = ''
		while N != 0:
			res = str(N % 9) + res
			N = N // 9
		return res


class Solution:

	def findNth(self, N):
		i = 0
		j = 0
		k = 1
		l = '9'
		while N > 0:
			i = i + k * (N % 9)
			N = N // 9
			k = k * 10
		return i


class Solution:

	def findNth(self, n):
		s = ''
		while n:
			s += str(n % 9)
			n //= 9
		return s[::-1]


class Solution:

	def findNth(self, n):
		sum = 0
		a = 1
		while n:
			sum += a * (n % 9)
			a *= 10
			n //= 9
		return sum


class Solution:

	def findNth(self, N):
		(answer, digit) = (0, 1)
		while N:
			answer += digit * (N % 9)
			digit *= 10
			N //= 9
		return answer


class Solution:

	def findNth(self, N):
		(res, i) = (0, 0)
		while N != 0:
			(N, rem) = divmod(N, 9)
			res += rem * pow(10, i)
			i += 1
		return res


class Solution:

	def findNth(self, N):
		res = 0
		base = 9
		t = 1
		while N > 0:
			res += N % base * t
			N = N // base
			t *= 10
		return res


import math

class Solution:

	def findNth(self, N):
		x = 0
		q = 1
		while N:
			x = x + q * (N % 9)
			q = q * 10
			N = N // 9
		return x


class Solution:

	def findNth(self, N):
		k = N
		list = []
		while k > 0:
			remainder = k % 9
			list.append(str(remainder))
			k = k // 9
		num_str = ''.join([list[i] for i in reversed(range(len(list)))])
		return int(num_str)


class Solution:

	def findNth(self, N):
		value = ''
		while N != 0:
			value = str(N % 9) + value
			N = N // 9
		return int(value)