Approach #1 Brute Force [Time Limit Exceeded]
Intuition
Simply create a list of all number upto an including n
without the numbers that don't contain 9
and then use the index to find the appropriate value.
Algorithm
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 1
.
Python
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]
Complexity Analysis

Time complexity : $$O(n)$$.
We need to grow our list until we haven
numbers, where none of them contains9
. 
Space complexity : $$O(n)$$.
We are storing alln
elements none of which contains9
.
Approach #2 Converting number to base 9
[Accepted]
Algorithm
A number without 9
essentially implies set of number base 9
. Therefore the solution is just (number)_{9}.
Python
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
Complexity Analysis

Time complexity : $$O(Log(n)$$. Here the # of iterations is Log_{9}(num). Hence the time complexity is $$O(Log(n)$$.

Space complexity: $$O(Log(n)$$, for storing all the remainders from the division.