Remove 9


  • 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 doesn'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 number has 9, if it does not have it then add it to the list and increment 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 set of 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.