Massive Algorithms: LeetCode 967 - Numbers With Same Consecutive Differences

LeetCode 967 - Numbers With Same Consecutive Differences

https://leetcode.com/problems/numbers-with-same-consecutive-differences/

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

1 <= N <= 9
0 <= K <= 9

https://www.acwing.com/solution/LeetCode/content/697/
(递归) O(2^N)
采用递归的方式，从高位开始逐一填数字，除最高位外，每一位最多有两种填法，分别尝试即可。
时间复杂度
最坏情况下，除最高位外，每一位都有两种填法，故时间复杂度为 O(2^N)

https://www.cnblogs.com/seyjs/p/10201645.html
但是有两点要注意的，一是K = 0 的情况会造成重复（+0和-0的值一样），二是N等于1的时候，别忘了0也是其中一个结果。
X. BFS
https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211183/JavaC%2B%2BPython-Iterative-Solution

We initial the current result with all 1-digit numbers,
like cur = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

Each turn, for each x in cur,
we get its last digit y = x % 10.
If y + K < 10, we add x * 10 + y + K to the new list.
If y - K >= 0, we add x * 10 + y + K to the new list.

We repeat this step N - 1 times and return the final result.

    public int[] numsSameConsecDiff(int N, int K) {
        List<Integer> cur = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
        for (int i = 2; i <= N; ++i) {
            List<Integer> cur2 = new ArrayList<>();
            for (int x : cur) {
                int y = x % 10;
                if (x > 0 && y + K < 10)
                    cur2.add(x * 10 + y + K);
                if (x > 0 && K > 0 && y - K >= 0)
                    cur2.add(x * 10 + y - K);
            }
            cur = cur2;
        }
        return cur.stream().mapToInt(j->j).toArray();
    }

Let's try to write some number in the answer digit by digit.

For each digit except the first, there are at most 2 choices for that digit. This means that there are at most

9 * 2^8

possible 9 digit numbers, for example. This is small enough to brute force.

N

digit number is just an

N-1

digit number with a final digit added. If the

N-1

digit number ends in a digit

d

, then the

N

digit number will end in

d-K

d+K

(provided these are digits in the range

[0,9]

). We store these numbers in a Set structure to avoid duplicates.

Also, we should be careful about leading zeroes -- only 1 digit numbers will start with 0.

Time Complexity: $O(2^N)$ .
Space Complexity: $O(2^N)$ .

public int[] numsSameConsecDiff(int N, int K) {

Set<Integer> cur = new HashSet();

for (int i = 1; i <= 9; ++i)

cur.add(i);

for (int steps = 1; steps <= N - 1; ++steps) {

Set<Integer> cur2 = new HashSet();

for (int x : cur) {

int d = x % 10;

if (d - K >= 0)

cur2.add(10 * x + (d - K));

if (d + K <= 9)

cur2.add(10 * x + (d + K));

}

cur = cur2;

}

if (N == 1)

cur.add(0);

int[] ans = new int[cur.size()];

int t = 0;

for (int x : cur)

ans[t++] = x;

return ans;

}

X. Using Queue
https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211433/Java-11-liner-BFSBacktrack

Initialize a queue with the most significant digits of candidate numbers: [1, 2, 3, 4, 5, 6, 7, 8, 9]; if N is 1, add 0 to the queue.
During every round of breadth search, the last digit of any given number, num, is k = num % 10.
If digit1 = k - K >= 0, append it to the end of num;
If digit2 = k + K < 10, and digit1 != digit2, append it to the end of num;
Repeat the above N - 1 times.

    public int[] numsSameConsecDiff(int N, int K) {
        Queue<Integer> q = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
        if (N == 1) { q.offer(0); } // in case N is 1.
        while (N-- > 1) {
            for (int sz = q.size(); sz > 0; --sz) {
                int num = q.poll();
                int digit1 = num % 10 - K, digit2 = num % 10 + K;
                if (digit1 >= 0) { q.offer(num * 10 + digit1); }
                if (digit2 < 10 && digit1 != digit2) { q.offer(num * 10 + digit2); }
            }
        }
        return q.stream().mapToInt(i -> i).toArray();
    }

X. DFS
https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211346/Simple-backtracking-with-explanation

this simply falls into backtracking problem template.

At each point, we can potentially:

add K to current digit
subtract k from current digit

and move to next step.

one edge case is to make sure that nextPlusK and nextMinusK hold different values, otherwise, there will be duplicate in the final results.

    public int[] numsSameConsecDiff(int N, int K) {
        
        ArrayList<Integer> allRes = new ArrayList();
        
        int begin = N == 1 ? 0 : 1;
        for (int i = begin; i <= 9 ; i++){
            backtrack(N, K, i, 0, i, allRes);
        }
        
        // copy to array
        return allRes.stream().mapToInt(j->j).toArray();
    }
    
    private void backtrack(int N, int K, int cur, int idx, int prev, ArrayList<Integer> allRes) {
        
        if (idx == N - 1) {
            allRes.add(cur);
            return;
        }
        
        int nextPlusK = prev + K;
        if (nextPlusK < 10){
            
            backtrack(N, K, (cur * 10) + nextPlusK, idx + 1, nextPlusK, allRes);
        }
        int nextMinusK = prev - K;
        
        if (nextMinusK != nextPlusK && nextMinusK >= 0){
            
            backtrack(N, K, (cur * 10) + nextMinusK, idx + 1, nextMinusK, allRes);
        }
    }

https://www.acwing.com/solution/LeetCode/content/697/
void solve(int depth, int num, int N, int K, vector<int> &ans) {
if (depth == 0) {
ans.push_back(num);
return;
}

if (depth == N) {
for (int i = 1; i <= 9; i++)
solve(depth - 1, i, N, K, ans);
if (N == 1)
solve(depth - 1, 0, N, K, ans);
}

else {
int last = num % 10;

if (last + K <= 9)
solve(depth - 1, num * 10 + last + K, N, K, ans);

if (K != 0 && last - K >= 0)
solve(depth - 1, num * 10 + last - K, N, K, ans);
}

}

vector<int> numsSameConsecDiff(int N, int K) {
vector<int> ans;
solve(N, 0, N, K, ans);

return ans;
}

Keep adding digits from 0 to 9 to a temporary integer at units place. Before adding we check if the digit being added is satisfying the condition of differing with previous digit by K. We add untill the temporary integer has N digits in it.

Start with the dfs function

fill the base cases first.

If the Number has enough digits, add it to the final list.
When the temporary integer is empty add all the digits except 0.

Later, fill the recursion for dfs.
Think about handling edge cases - What should be returned if N = 0, N = 1 (where 0 should appear in end result) or K = 1 ?

public int[] numsSameConsecDiff(int N, int K) {
        List<Integer> list = new ArrayList<>();
        if(N==0)
            return new int[0];
        if(N==1)
   list.add(0);      // edge case
        dfs(N, K, list, 0);
        return list.stream().mapToInt(i->i).toArray();   //list.toArray(new int[list.size()]); doesn't work for primitives
    }
    public void dfs(int N, int K, List<Integer> list, int number){
        if(N == 0){   // base case, if you have added enough number of integers then append it to list; Here N is used as the total digits in temporary number 
            list.add(number);
            return ;
        }
        for(int i=0; i<10; ++i){
            if(i==0 && number ==0)    // Do not add 0 at begining of a number
                continue;
            else if(number == 0 && i!=0){     // base case, we add all the digits when we do not have any previous digit to check if difference = K
                dfs(N-1, K, list, i);
            }
            else{
                if(Math.abs((number%10) - i )==K){
                    dfs(N-1, K, list, number*10+i);    // General dfs to add the digit at the units place and reducing the number of digits by 1.
                }
            }
        }
    }

X. https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211346/Simple-backtracking-with-e

At each point, we can potentially:

add K to current digit
subtract k from current digit

and move to next step.

one edge case is to make sure that nextPlusK and nextMinusK hold different values, otherwise, there will be duplicate in the final results.

    public int[] numsSameConsecDiff(int N, int K) {
        
        ArrayList<Integer> allRes = new ArrayList();
        
        int begin = N == 1 ? 0 : 1;
        for (int i = begin; i <= 9 ; i++){
            backtrack(N, K, i, 0, i, allRes);
        }
        
        // copy to array
        return allRes.stream().mapToInt(j->j).toArray();
    }
    
    private void backtrack(int N, int K, int cur, int idx, int prev, ArrayList<Integer> allRes) {
        
        if (idx == N - 1) {
            allRes.add(cur);
            return;
        }
        
        int nextPlusK = prev + K;
        if (nextPlusK < 10){
            
            backtrack(N, K, (cur * 10) + nextPlusK, idx + 1, nextPlusK, allRes);
        }
        int nextMinusK = prev - K;
        
        if (nextMinusK != nextPlusK && nextMinusK >= 0){
            
            backtrack(N, K, (cur * 10) + nextMinusK, idx + 1, nextMinusK, allRes);
        }
    }

LeetCode 967 - Numbers With Same Consecutive Differences

Labels

Popular Posts