We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Numbers With Same Consecutive Differences

Difficulty: Medium

Problem Description

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order. Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

Key Insights

  • The problem involves generating numbers of a specific length with constraints on the differences between consecutive digits.
  • The digits must be chosen such that they do not lead to invalid numbers (like leading zeros).
  • Backtracking is a suitable approach to explore the possible digits recursively.
  • A breadth-first search (BFS) approach can also be used to build numbers level by level.

Space and Time Complexity

Time Complexity: O(2^n) - In the worst case, each digit can lead to two possible choices for the next digit. Space Complexity: O(n) - The stack space used by recursion or the space used for BFS.

Solution

To solve this problem, we can use a backtracking approach. We will start building numbers from each possible starting digit (1 to 9) and recursively add digits that differ from the last added digit by k. We need to ensure that we only form valid numbers of length n and avoid leading zeros.

We will use an array to store the results and a helper function to perform the backtracking. The function will append digits to the current number and will be called recursively until the number reaches the desired length.

Code Solutions

def numbersSameConsecDiff(n, k):
    result = []

    def backtrack(num):
        if len(num) == n:
            result.append(int(num))
            return

        last_digit = int(num[-1])
        # Calculate the next possible digits
        next_digits = set()
        if last_digit + k < 10:
            next_digits.add(last_digit + k)
        if last_digit - k >= 0:
            next_digits.add(last_digit - k)

        for next_digit in next_digits:
            backtrack(num + str(next_digit))

    # Start from each digit from 1 to 9
    for i in range(1, 10):
        backtrack(str(i))

    return result
← Back to All Questions