Solution by pingu92


  • 0
    P

    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.


Log in to reply
 

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