Approach #1 Brute Force [Time Limit Exceeded]
Simply create a list of all number up-to an including
n without the numbers that doesn't contain
9 and then use the index to find the appropriate value.
Suppose we have a function
def newInteger(self, n):. We can start by creating an empty list. Start from number
1 (current_number) and keep moving one step ahead, check whether the string representation of number has
9, if it does not have it then add it to the list and increment current number by
class Solution(object): def newInteger(self, n): """ :type n: int :rtype: int """ current_number = 1 newList =  while current_number <= n: if '9' in str(current_number): n += 1 else: newList.append(current_number) current_number += 1 return newList[-1]
Time complexity : $$O(n)$$.
We need to grow our list until we have
nnumbers, where none of them contains
Space complexity : $$O(n)$$.
We are storing all
nelements none of which contains
Approach #2 Converting number to base
A set of number without
9 essentially implies set of number base
9. Therefore the solution is just (number)9.
class Solution(object): def newInteger(self, n): """ :type n: int :rtype: int """ result = '' while n: result += str(n%9) n /= 9 return int(result[::-1]) # reverses the result string
Time complexity : $$O(Log(n)$$. Here the # of iterations is Log9(num). Hence the time complexity is $$O(Log(n)$$.
Space complexity : $$O(Log(n)$$, for storing all the remainders from the division.