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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Numbers With Same Consecutive Differences

Number: 1007

Difficulty: Medium

Paid? No

Companies: Flipkart

Problem Description

Given two integers n and k, return an array of all n-digit integers such that the absolute difference between every two consecutive digits equals k. Note that integers with leading zeros are not allowed.

Key Insights

  • Start constructing numbers from digits 1 through 9 to avoid leading zeros.
  • Use backtracking (or BFS) to add one digit at a time, ensuring the difference between consecutive digits equals k.
  • At each step, explore the two possible next digits: current_digit + k and current_digit - k (if within bounds 0 to 9).
  • Handle the edge case when k is 0, as it does not produce two distinct possibilities.

Space and Time Complexity

Time Complexity: O(2^(n)) in the worst case, as each number can branch into up to 2 choices for each new digit. Space Complexity: O(n) due to recursion depth (or queue depth in a BFS approach) along with the space needed for the output.

Solution

We solve the problem using a backtracking approach. The idea is to build each valid n-digit number digit by digit, starting from a non-zero digit. At each step, we look at the last digit and calculate the possible next digits using the rule: next_digit = last_digit ± k. We add the new digit if it is within the range [0, 9] and continue until the number reaches length n. If k equals 0, then both options yield the same digit so we only need to add one. The built number is then added to the results once the required length is reached.

Code Solutions

# Python solution
class Solution:
    def numsSameConsecDiff(self, n: int, k: int):
        # List to store the valid numbers
        results = []
        
        # Backtracking helper function
        def backtrack(number, digits_count):
            # If the number has reached the required number of digits, add to results
            if digits_count == n:
                results.append(number)
                return
            # Get the last digit of the current number
            last_digit = number % 10
            # Calculate the next possible digits and try them if they are in range 0-9
            next_digits = set([last_digit + k, last_digit - k])
            for next_digit in next_digits:
                if 0 <= next_digit <= 9:
                    # Append the digit and increase digit count
                    backtrack(number * 10 + next_digit, digits_count + 1)
        
        # Begin backtracking with digits 1 to 9 (avoid leading zero)
        for digit in range(1, 10):
            backtrack(digit, 1)
        
        return results

# Example usage:
# sol = Solution()
# print(sol.numsSameConsecDiff(3, 7))
← Back to All Questions