# Solution by pingu92

• #### Approach #1 Brute Force [Time Limit Exceeded]

Intuition

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.

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 have `n` numbers, where none of them contains `9`.

• Space complexity : \$\$O(n)\$\$.
We are storing all `n` elements none of which contains `9`.

#### 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 Log9(num). Hence the time complexity is \$\$O(Log(n)\$\$.

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.