A general solution in java, useful if some number other than 9 is removed


  • 1
    M

    The radix solution to this problem is cool. However, what if the question requests to remove some other number? e.g. to remove 4, or even remove both 4 and 7.

    Here, I will give a general solution to this kind of questions.

    General ideas:
    The question is "Given a positive integer n, you need to return the n-th integer after removing (remove 9 in this question)". Assume we got the result, x, which means that within the range [1, x], there are (x - n) integers that contains 9, right?

    First, we'd like to find a method to get "how many integers contains 9 within the range [1, x]".
    let's see the regular pattern in each range:
    [1-9] = 1
    [10-89] = 9
    [90-99] = 10
    => [10-99] = [10-89] + [90-99]
    [100-899] = 9 * [10-99]
    [900-999] = 100
    => [100-999] = [100-899] + [900-999]
    [1000-8999] = 9 * [100-999]
    [9000-9999] = 1000
    [1000-9999] = [1000-8999] + [9000-9999]
    ...
    Thus, we can use dynamic programming to get the number of integers that contains 9 in each [10^n, 10^(n + 1) - 1] range. Then, for a specific number, we can split this number digit by digit.
    For example: given an integer 74925
    [1-74925] = [1-69999] + [70000 -74925] = 7 * [1-9999] + [70000 -74925]
    [70000 -74925] = [1-4925]
    we've already got the [1-9999], so we continue to split [1-4925]
    [1-4925] = [1-3999] + [4000-4925] = 4 * [1-999] + [1-925]
    again, we got [1-999], continue:
    [1-925] = [1-899] + [900-925] = 9 * [1-99] + [900-925]
    Here, we should take notice: within this range [900-925] every integer contains 9. Therefore, we do not need to split this range any more (It means, from left to right, once you hit the first 9, no need to split the number any more)
    [900-925] = 25 + 1
    Let's review the procedure:
    74925 = 7 * [1-9999] + 4 * [1-999] + 9 * [1-99] + 25 + 1;
    It seems we got the method "numOf9" to find how many integers contains 9 within [1,x].

    Second, I think no need to talk too much, we can use binary search to find x, where "x - numOf9(x) == n"
    BUT, I'd like to emphasize that x should not contains 9. Thus, pay a little more attention during binary search to make x not contains 9.

    public class Solution {
        int[] dp;
        public int newInteger(int n) {
            if (n < 9) return n;
            dp = new int[10];  
           //dp[n] corresponds to range[10^(n - 1), 10^n - 1], e.g. dp[2] is the number of 9 within [10, 99]
            dp[0] = 0;
            dp[1] = 1;
            int p = 10;
            for (int i = 2; i < 10; i++) {
                dp[i] = dp[i - 1] * 9 + p;
                p *= 10;
            }
            int left = n;
            int right = Integer.MAX_VALUE;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (mid - numOf9(mid) >= n) {  // make sure the result does not contains 9
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
        private int numOf9(int x) {  // 10 <= x <= MAX_INT 
            int res = 0;
            int num = x;
            int i = 0;
            int p = 1;
            while (num != 0) {
                int lastdigit = num % 10;
                if (lastdigit == 9) {
                    res = 9 * dp[i] + x % p + 1;
                } else {
                    res += lastdigit * dp[i];
                }
                i++;
                p *= 10;
                num /= 10;
            }
            return res;
        }
    }
    

Log in to reply
 

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