Leetcode journey - Question 967 - Numbers With Same Consecutive Differences

Problem:

Q967. 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. For example, 01 has one leading zero and is invalid.

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]

Constraints:

• 2 <= n <= 9
• 0 <= k <= 9

Solution:

Approach 1:

We can use a recursive approach to solve this problem. We can make a recursive function which takes the number of digits left(n), the difference between the digits(K), the number formed till now(num) and the answer vector(ans) as the parameters.
We will start with a digit(1-9) and then check either the digit + k is less than or equal to 9 or digit - k is greater than or equal to 0 (if k is not equal to 0).
If yes, then we will call the function recursively with n - 1, k, num * 10 + lastDigit + k and if no, then we will return and continue the process until the length of the number is equal to n.

for example if n = 3 and k = 2 and suppose we start with 4 and then check if 4 + 2 is less than or equal to 9 or 4 - 2 is greater than or equal to 0. It turns both are true and our next digit can be either 6 or 2.
So we will call the function recursively with function(n - 1, k, num * 10 + 6) and also with function(n - 1, k, num * 10 + 2).

We will continue the process until the length of the number is equal to n.
If the length of the number is equal to n, then we will push the number in the answer vector and return.
Now, Lets look at the pseudo code:

Pseudo Code:

recurse_function(n, k, num, ans)
    if n == 0
        push num in ans
        return
    lastDigit = num % 10
    if lastDigit + k = 0 and k != 0
        function(n - 1, k, num * 10 + lastDigit - k, ans)

function(n, k)
    loop from 1 to 9
        call function(n - 1, k, i, ans)
    print ans

Now, we can write the code:

Code:

class Solution
{
public:
    void recurse(int n, int k, int num, vector<int> &ans)
    {
        if (n == 0)
        {
            ans.push_back(num);
            return;
        }
        int lastDigit = num % 10;
        if (lastDigit + k <= 9)
        {
            recurse(n - 1, k, num * 10 + lastDigit + k, ans);
        }
        if (lastDigit - k >= 0 && k != 0)
        {
            recurse(n - 1, k, num * 10 + lastDigit - k, ans);
        }
    }
    vector<int> numsSameConsecDiff(int n, int k)
    {
        vector<int> ans;
        for (int i = 1; i <= 9; i++)
        {
            recurse(n - 1, k, i, ans);
        }
        return ans;
    }
};

Complexity Analysis:

Time Complexity: O(2^n)
Space Complexity: O(2^n)

Approach 2:

We can use a queue to solve this problem. We will create a for loop from 1 to 9 and push each number in the queue. inside the loop we will create two variables left_limit (10^(n-1)) and right_limit (10^n-1), then we will create a while loop which will run until the queue is empty. we will pop the number from the queue and check if it is in the range of left_limit and right_limit.
If yes, then we will push it in the answer vector.
If no, then we will extract the last digit of the number inside a variable lastDigit.
Then we will check if lastDigit + k is less than or equal to 9 or lastDigit - k is greater than or equal to 0 (if k is not equal to 0).
If yes, then we will push the number * 10 + lastDigit + k and num * 10 + lastDigit - k in the queue respectively and continue the process until the queue is empty.
Now, Lets look at the pseudo code:

Pseudo Code:

function numsSameConsecDiff(n, k)
    ans = []
    left_limit = 10^(n-1)
    right_limit = 10^n-1
    for i = 1 to 9
       push i in queue
       while queue is not empty
           num = pop from queue
           if num is in the range of left_limit and right_limit
               push num in ans
               continue
           lastDigit = num % 10
           if lastDigit + k <= 9
               push num * 10 + lastDigit + k in queue
           if lastDigit - k >= 0 and k != 0
               push num * 10 + lastDigit - k in queue
    return ans
 

Now let's try to code it in c++.

Code in C++:

class Solution
{
public:
    void recurse(int n, int k, int num, vector<int> &ans)
    {
        if (n == 0)
        {
            ans.push_back(num);
            return;
        }
        int lastDigit = num % 10;
        if (lastDigit + k <= 9)
        {
            recurse(n - 1, k, num * 10 + lastDigit + k, ans);
        }
        if (lastDigit - k >= 0 && k != 0)
        {
            recurse(n - 1, k, num * 10 + lastDigit - k, ans);
        }
    }
    vector<int> numsSameConsecDiff(int n, int k)
    {
        vector<int> ans;
        for (int i = 1; i <= 9; i++)
        {
            recurse(n - 1, k, i, ans);
        }
        return ans;
    }
};

Complexity Analysis:

Time Complexity: O(2^n)
Space Complexity: O(2^n)
Hope this helps!

• If you have any questions, please leave a comment below. 💭
  

• If you like this article, please share it with your friends. 💖
  

• If you want to read more articles like this, please follow me.
  

Thank you for reading!