Given an integer N, You need to find the Nth smallest number which only contains odd digits i.e. 1,3,5,7,9 means no even digits are allowed on that number (12 will not consider). For example, the starting numbers which only contain odd digits are 1,3,5,7,9,11,13,15,17,19,31,33,35 and so on.
Example 1:
Input:
N=3
Output:
5
Explanation:
First three numbers are 1, 3, 5.
Here 5 is the 3rd number, where contains
only odd digits.
Example 2:
Input:
N=13
Output:
35
Explanation:
First 13 numbers are 1,3,5,7,9,
11,13,15,17,19,31,33,35, here 35 
is the answer.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findNumber() which takes a single variable N and returns the smallest Nth number which only contains odd digits.
Expected Time Complexity: O(logN)
Expected Space Complexity: O(1)
Constraints:
1 <= N <= 10^12

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3

 class Solution:

    def findNumber(self, N : int) -> int:

        # code here

        

Solutions:
class Solution:

	def findNumber(self, N: int) -> int:
		if N == 0:
			return 0
		N -= 1
		return 10 * self.findNumber(N // 5) + 2 * (N % 5) + 1


class Solution:

	def findNumber(self, N: int) -> int:

		def help(n):
			if n < 6:
				return n + (n - 1)
			if n % 5 == 0:
				return help(n // 5 - 1) * 10 + 9
			else:
				return help(n // 5) * 10 + n % 5 + n % 5 - 1
		return help(N)


class Solution:

	def findNumber(self, N: int) -> int:
		odd_numbers = [1, 3, 5, 7, 9]
		if N <= 5:
			return odd_numbers[(N - 1) % 5]
		n_mod_5 = N % 5
		if not n_mod_5:
			return self.findNumber((N - 1) // 5) * 10 + odd_numbers[(N - 1) % 5]
		else:
			return self.findNumber(N // 5) * 10 + odd_numbers[(N - 1) % 5]


class Solution:

	def findNumber(self, N: int) -> int:
		ans_add = N * 2 - 1
		ans = 0
		subtract = 0
		divide = 1
		multiply = 1
		while ans_add > 0:
			ans += ans_add
			subtract += divide
			divide *= 5
			multiply *= 10
			ans_add = ((N - subtract) // divide - 1) * multiply
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		l = [9, 1, 3, 5, 7]
		s = ''
		if N == 5:
			return 9
		elif N <= 4:
			return l[N]
		if N > 5:
			v = N % 5
			s += str(l[v])
			k = N // 5
			if v == 0:
				k = k - 1
			if k > 4:
				while k > 4:
					i = k % 5
					if k != 5:
						s += str(l[i])
					k = k // 5
					if i == 0:
						k = k - 1
			s += str(l[k])
			p = int(s[::-1])
			return p


class Solution:

	def findNumber(self, N: int) -> int:
		res_list = []
		odd_list = [1, 3, 5, 7, 9]
		remainder = 0
		quotient = N
		res = 0
		tens = 1
		while quotient:
			remainder = quotient % 5
			quotient = quotient // 5
			if remainder == 0:
				res_list.append(odd_list[4])
				quotient -= 1
			else:
				res_list.append(odd_list[remainder - 1])
		for i in res_list:
			res += i * tens
			tens *= 10
		return res


class Solution:

	def findNumber(self, N: int) -> int:
		d = {1: 1, 2: 3, 3: 5, 4: 7, 0: 9}
		n = N
		ans = 0
		multipler = 1
		while n > 0:
			(n, r) = divmod(n, 5)
			if r == 0:
				n -= 1
			ans += multipler * d[r]
			multipler *= 10
		return ans


class Solution:

	def findNumber(self, n: int) -> int:
		l = ['9', '1', '3', '5', '7']
		x = n
		s = ''
		while n > 0:
			if n % 5 == 0:
				s += l[n % 5]
				n //= 5
				n -= 1
			else:
				s += l[n % 5]
				n //= 5
		return s[-1::-1]


def _findNumber(pv, fv, add):
	fv = int(fv / 5) - 1
	if fv <= 0:
		return 0
	add = _findNumber(pv * 10, fv, add) + fv * pv
	return add

class Solution:

	def findNumber(self, N):
		ans = 1
		if N > 1:
			pv = 2
			fv = N - 1
			ans = _findNumber(10, fv, 0) + fv * pv + 1
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		arr = [9, 1, 3, 5, 7]
		curr = 1
		ans = 0
		while N > 0:
			ans = arr[N % 5] * curr + ans
			if N % 5 == 0:
				N = int(N / 5) - 1
			else:
				N = int(N / 5)
			curr = curr * 10
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		d = [1, 3, 5, 7, 9]
		if N <= 5:
			return d[N - 1]
		if N >= 6 and N <= 10:
			return '1' + str(d[N % 5 - 1])
		s = ''
		while N > 0:
			p = N % 5 - 1
			if p == -1:
				N = N // 5 - 1
			else:
				N //= 5
			s = str(d[p]) + s
		return int(s)


class Solution:

	def findNumber(self, N: int) -> int:
		odd = [1, 3, 5, 7, 9]
		digit = []
		ans = 0
		t = 1
		qu = N
		while qu:
			rem = qu % 5
			qu = qu // 5
			if rem == 0:
				digit.append(odd[4])
				qu -= 1
			else:
				digit.append(odd[rem - 1])
		for i in digit:
			ans += i * t
			t *= 10
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		ans = 0
		while N:
			if N % 5 == 0:
				ans = ans * 10 + 9
			elif N % 5 == 1:
				ans = ans * 10 + 1
			elif N % 5 == 2:
				ans = ans * 10 + 3
			elif N % 5 == 3:
				ans = ans * 10 + 5
			elif N % 5 == 4:
				ans = ans * 10 + 7
			if N % 5 == 0:
				N = N // 5 - 1
			else:
				N = N // 5
		return self.reverse(ans)

	def reverse(self, num):
		res = 0
		while num > 0:
			res = res * 10 + num % 10
			num = num // 10
		return res


class Solution:

	def findNumber(self, N: int) -> int:
		a = [9, 1, 3, 5, 7]
		ans = 0
		cur = 1
		while N > 0:
			ans += a[N % 5] * cur
			if N % 5 == 0:
				N = N // 5 - 1
				cur *= 10
			else:
				N = N // 5
				cur *= 10
		return ans


from math import log

class Solution:

	def findNumber(self, N: int) -> int:
		remainders = {0: '1', 1: '3', 2: '5', 3: '7', 4: '9'}
		a = [(0, 0)]
		counter = 1
		count = 5
		while N > count:
			a.append((counter, count))
			counter += 1
			count += 5 ** counter
		ans = ''
		cur = N
		for (counter, count) in a[::-1]:
			d = (cur - count - 1) // 5 ** counter
			ans += remainders[d]
			cur -= 5 ** counter * (d + 1)
		return int(ans)


class Solution:

	def findNumber(self, N: int) -> int:
		mp = {0: 1, 1: 3, 2: 5, 3: 7, 4: 9}

		def soln(N):
			if not N:
				return 0
			if N < 5:
				return mp[N - 1]
			q = N // 5
			r = N % 5
			if not r:
				q -= 1
				r = (r - 1) % 5 + 1
			return soln(q) * 10 + mp[r - 1]
		return soln(N)


class Solution:

	def findNumber(self, N: int) -> int:
		a = [1, 3, 5, 7, 9]
		s = ''
		pre = 1
		mul = 5
		times = 2
		while N > 0:
			temp = N % mul - 1
			ind = (temp + mul) % mul
			index = ind // pre
			s = str(a[index]) + s
			N -= mul
			mul = mul * 5
			times += 1
			pre *= 5
		return s


class Solution:

	def findNumber(self, N: int) -> int:
		if N <= 5:
			if N == 0:
				return 9
			elif N == 1:
				return 1
			elif N == 2:
				return 3
			elif N == 3:
				return 5
			elif N == 4:
				return 7
			elif N == 5:
				return 9
		if N % 10 == 0 or N % 5 == 0:
			x = N - 1
		else:
			x = N
		ans = self.findNumber(x // 5)
		a = N % 10
		if N % 10 == 0:
			a = 10
		ld = (2 * a - 1) % 10
		ans = ans * 10 + ld
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		return self.get_num(N)

	def get_num(self, x):
		nums = (1, 3, 5, 7, 9)
		res = ''
		if not x:
			return ''
		if x != 5:
			res = self.get_num((x - 1) // 5)
		return res + str(nums[(x - 1) % 5])


class Solution:

	def findNumber(self, N: int) -> int:
		v = [9, 1, 3, 5, 7]
		ans = 0
		while N > 0:
			ans = ans * 10 + v[N % 5]
			if N % 5 == 0:
				N = N // 5
				N = N - 1
			else:
				N = N // 5
		q = []
		while ans > 0:
			q.append(ans % 10)
			ans = ans // 10
		while len(q) > 0:
			ans = ans * 10 + q[0]
			q.pop(0)
		return ans


class Solution:

	def findNumber(self, n: int) -> int:
		if n == 0 or n == 5:
			return 9
		elif n == 1:
			return 1
		elif n == 2:
			return 3
		elif n == 3:
			return 5
		elif n == 4:
			return 7
		elif n % 5 == 0:
			return 10 * self.findNumber(n // 5 - 1) + 9
		else:
			return 10 * self.findNumber(n // 5) + self.findNumber(n % 5)


class Solution:

	def findNumber(self, N: int) -> int:
		counts = [5]
		numbers = [1, 3, 5, 7, 9]
		times = 0
		while N > counts[times]:
			N -= counts[times]
			counts.append(counts[times] * 5)
			times += 1
		N = N - 1
		r = []
		for i in range(times + 1):
			(N, j) = (N // 5, N % 5)
			r.append(j)
		x = 0
		for (i, e) in enumerate(r):
			x += numbers[e] * 10 ** i
		return x


from math import *

class Solution:

	def digitSize(self, N):
		s = 1
		val = 5
		while N > val:
			N -= val
			val *= 5
			s += 1
		return (N, s)

	def rem(self, val, div):
		r = val % div
		if r == 0:
			return div
		return r

	def findNumber(self, N: int) -> int:
		(N, s) = self.digitSize(N)
		ans = 0
		while s:
			s -= 1
			t = ceil(N / 5 ** s)
			ans = 10 * ans + (2 * t - 1)
			N = self.rem(N, 5 ** s)
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		c = 0
		while N != 0:
			c = c * 10
			if N % 5 == 0:
				c += 9
				N = N // 5
				N -= 1
			elif N % 5 == 1:
				c += 1
				N = N // 5
			elif N % 5 == 2:
				c += 3
				N = N // 5
			elif N % 5 == 3:
				c += 5
				N = N // 5
			elif N % 5 == 4:
				c += 7
				N = N // 5
		a = 0
		while c != 0:
			a = a * 10 + c % 10
			c = c // 10
		return a


class Solution:

	def findNumber(self, N: int) -> int:
		a = [9, 1, 3, 5, 7]
		c = 0
		d = 1
		while N > 0:
			b = int(N % 5)
			c = c + a[b] * d
			d = d * 10
			if N % 5 == 0:
				N -= 1
			N = N // 5
		return c


class Solution:

	def findNumber(self, N: int) -> int:
		ans = 0
		while N:
			ans *= 10
			if N % 5 == 0:
				ans += 9
				N = N // 5
				N -= 1
			elif N % 5 == 1:
				ans += 1
				N //= 5
			elif N % 5 == 2:
				ans += 3
				N //= 5
			elif N % 5 == 3:
				ans += 5
				N //= 5
			else:
				ans += 7
				N //= 5
		return str(ans)[::-1]


from queue import Queue

class Solution:

	def findNumber(self, N: int) -> int:
		v = [9, 1, 3, 5, 7]
		ans = 0
		while N > 0:
			ans = ans * 10 + v[N % 5]
			if N % 5 == 0:
				N = N // 5
				N -= 1
			else:
				N //= 5
		q = Queue()
		while ans > 0:
			q.put(ans % 10)
			ans //= 10
		while not q.empty():
			ans = ans * 10 + q.get()
		return ans


class Solution:

	def findNumber(self, n: int) -> int:
		ans = 0
		base5 = list()
		while n:
			n -= 1
			base5.append(n % 5)
			n //= 5
		for x in base5[::-1]:
			ans = ans * 10 + 2 * x + 1
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		dit = {0: 9, 1: 1, 2: 3, 3: 5, 4: 7}
		ans = 0
		p = 1
		while N > 0:
			r = N % 5
			ans += p * dit[r]
			N = N // 5 - (r == 0)
			p *= 10
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		(soln, prod) = (0, 5)
		digit = 1
		while N - prod > 0:
			N -= prod
			prod *= 5
			digit += 1
		for i in range(1, digit + 1):
			for j in range(1, 10, 2):
				temp = 5 ** (digit - i)
				if temp == 0:
					soln = soln * 10 + 2 * N - 1
					break
				if N - temp > 0:
					N -= temp
				else:
					soln = soln * 10 + j
					break
		return soln


class Solution:

	def findNumber(self, N: int) -> int:
		res_l = []
		odd_l = [1, 3, 5, 7, 9]
		r = 0
		q = N
		res = 0
		te = 1
		while q:
			r = q % 5
			q = q // 5
			if r == 0:
				res_l.append(odd_l[4])
				q -= 1
			else:
				res_l.append(odd_l[r - 1])
		for i in res_l:
			res += i * te
			te *= 10
		return res


class Solution:

	def findNumber(self, N: int) -> int:
		dit = {0: '1', 1: '1', 2: '3', 3: '5', 4: '7', 5: '9'}
		ans = ''
		while N > 0:
			r = N % 5
			if r == 0:
				ans += str(dit[5])
				N = N // 5 - 1
			else:
				ans += str(dit[r])
				N = N // 5
		return int(ans[::-1])


class Solution:

	def findNumber(self, N: int) -> int:
		num = 0
		lst = [9, 1, 3, 5, 7]
		x = 1
		p = 1
		while N != 0:
			lastDigit = N % 5
			num = num + lst[lastDigit] * p
			if N % 5 == 0:
				N -= 1
			p *= 10
			N = N // 5
		return num


class Solution:

	def findNumber(self, N: int) -> int:
		a = [1, 3, 5, 7, 9]
		if N <= 5:
			return a[N - 1]

		def sub(N: int):
			b = N % 5
			if N % 5 == 0:
				b = 5
			c = int(N / 5)
			if N / 5 == c:
				c = c - 1
			c = c - 1
			i = 0
			if c >= 10:
				i = sub(c + 1)
			else:
				i = 1 + c * 2
			j = a[b - 1]
			return i * 10 + j
		x = sub(N)
		return x


class Solution:

	def findNumber(self, N: int) -> int:
		ans = 0
		lst = [9, 1, 3, 5, 7]
		ans = 0
		p = 1
		while N != 0:
			rem = N % 5
			ans += lst[rem] * p
			if N % 5 == 0:
				N -= 1
			p *= 10
			N //= 5
		return ans


class Solution:

	def findNumber(self, N: int) -> int:
		arr2 = [1, 3, 5, 7, 9]
		rem = 0
		arr = []
		while N > 0:
			rem = N % 5
			N = N // 5
			if rem == 0:
				arr.append(9)
				N -= 1
			else:
				arr.append(arr2[rem - 1])
		unit = 1
		sum = 0
		for i in arr:
			sum = sum + i * unit
			unit = unit * 10
		return sum


class Solution:

	def findNumber(self, N: int) -> int:
		a = [9, 1, 3, 5, 7]
		res = []
		while N > 0:
			res.append(str(a[N % 5]))
			if N % 5 == 0:
				N = N // 5 - 1
			else:
				N = N // 5
		res.reverse()
		res = ''.join(res)
		return res