Formatted question description: https://leetcode.ca/all/967.html

967. Numbers With Same Consecutive Differences (Medium)

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. 1 <= N <= 9
  2. 0 <= K <= 9

Related Topics:
Dynamic Programming

Solution 1.

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

// Time: O(N)
// Space: O(N)
class Solution {
    vector<int> ans;
    void dfs(int num, int i, int N, int K) {
        if (i == N) {
            ans.push_back(num);
            return;
        }
        if (num % 10 + K <= 9) dfs(num * 10 + (num % 10 + K), i + 1, N, K);
        if (K != 0 && num % 10 - K >= 0) dfs(num * 10 + (num % 10 - K), i + 1, N, K);
    }
public:
    vector<int> numsSameConsecDiff(int N, int K) {
        for (int i = N == 1 ? 0 : 1; i <= 9; ++i) dfs(i, 1, N, K);
        return ans;
    }
};

Java

  • class Solution {
        public int[] numsSameConsecDiff(int N, int K) {
            if (N == 1) {
                int[] nums = new int[10];
                for (int i = 0; i < 10; i++)
                    nums[i] = i;
                return nums;
            }
            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i = 1; i <= 9; i++) {
                int nextDigit1 = i - K, nextDigit2 = i + K;
                if (nextDigit1 >= 0)
                    queue.offer(i * 10 + nextDigit1);
                if (K != 0 && nextDigit2 < 10)
                    queue.offer(i * 10 + nextDigit2);
            }
            for (int digits = 3; digits <= N; digits++) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int num = queue.poll();
                    int lastDigit = num % 10;
                    int nextDigit1 = lastDigit - K, nextDigit2 = lastDigit + K;
                    if (nextDigit1 >= 0)
                        queue.offer(num * 10 + nextDigit1);
                    if (K != 0 && nextDigit2 < 10)
                        queue.offer(num * 10 + nextDigit2);
                }
            }
            int length = queue.size();
            int[] nums = new int[length];
            for (int i = 0; i < length; i++)
                nums[i] = queue.poll();
            return nums;
        }
    }
    
  • // OJ: https://leetcode.com/problems/numbers-with-same-consecutive-differences/
    // Time: O(N)
    // Space: O(N)
    class Solution {
        vector<int> ans;
        void dfs(int num, int i, int N, int K) {
            if (i == N) {
                ans.push_back(num);
                return;
            }
            if (num % 10 + K <= 9) dfs(num * 10 + (num % 10 + K), i + 1, N, K);
            if (K != 0 && num % 10 - K >= 0) dfs(num * 10 + (num % 10 - K), i + 1, N, K);
        }
    public:
        vector<int> numsSameConsecDiff(int N, int K) {
            for (int i = N == 1 ? 0 : 1; i <= 9; ++i) dfs(i, 1, N, K);
            return ans;
        }
    };
    
  • class Solution(object):
        def numsSameConsecDiff(self, N, K):
            """
            :type N: int
            :type K: int
            :rtype: List[int]
            """
            if N == 1:
                return [0, 1,2,3,4,5,6,7,8,9]
            res = []
            for i in range(1, 10):
                self.dfs(res, i, N - 1, K)
            return list(set(res))
            
        def dfs(self, res, curint, N, K):
            if N == 0:
                res.append(curint)
                return
            last = curint % 10
            if last + K <= 9:
                self.dfs(res, curint * 10 + last + K, N - 1, K)
            if last - K >= 0:
                self.dfs(res, curint * 10 + last - K, N - 1, K)
    

All Problems

All Solutions