Approach #1 Brute Force [Time Limit Exceeded]
Simply create a list of all number up-to an including
n without the numbers that don'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 a number has
9, if it does not have it then add it to the list and increment the 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 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.