Jobs

Interviews

Discussions

Numbers With Same Consecutive Differences

Medium

Asked by:

12 views

Topics:

Recursion

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.

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

Numbers With Same Consecutive Differences

Medium

Asked by:

12 views

Topics:

Recursion

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.

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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for the digits `n` and `k`? Specifically, what are the maximum and minimum possible values for `n` and `k`?
Should I return the numbers with `n` digits as a list of integers or as a list of strings?
If `k` is 0, are consecutive digits allowed to be the same?
Should the output list be sorted in any particular order, such as ascending or descending?
Are leading zeros permitted in the generated numbers (e.g., if n=2, can '07' be considered a valid number)?

Brute Force Solution

Approach

The brute force method creates all possible numbers that meet our requirements. We'll start by building numbers digit by digit, checking if the difference between adjacent digits matches what we want. We'll keep only the numbers that fit the requested length and meet the difference criteria.

Here's how the algorithm would work step-by-step:

Start with each single-digit number as a potential starting point.
For each potential number, try adding another digit at the end.
Check if the difference between the new digit and the last digit of the current number matches the allowed difference.
If it matches, keep the new, longer number and repeat the process of adding another digit.
If it doesn't match, discard that possibility and try a different digit.
Continue adding digits until the number reaches the required length.
If a number reaches the required length while still following the difference rule, save it.
Repeat this whole process starting from each possible single-digit number.
Finally, return all the saved numbers that satisfy the conditions.

Code Implementation

def numbers_with_same_consecutive_differences(number_length, difference):
    results = []

    # Iterate through single digit numbers as starting points
    for starting_digit in range(1, 10):
        def generate_numbers(current_number):
            if len(str(current_number)) == number_length:
                results.append(current_number)
                return

            last_digit = int(str(current_number)[-1])

            # Check possible next digits based on the difference
            possible_next_digits = [last_digit + difference, last_digit - difference]

            for next_digit in possible_next_digits:
                # Validate next digit to be from 0 to 9
                if 0 <= next_digit <= 9:
                    generate_numbers(current_number * 10 + next_digit)

        generate_numbers(starting_digit)

    # Remove duplicate numbers
    return list(set(results))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(10 * 2^N) – The algorithm explores all possible N-digit numbers where the difference between consecutive digits is K. For each digit, there are at most two choices (last digit + K or last digit - K), which leads to a branching factor of 2 at each level of recursion up to length N. Since we start from 1 to 9 inclusive, we have 9 starting points. Each starting point could theoretically generate at most approximately 2^(N-1) valid sequences (this approximation assumes K doesn't prevent branching). Therefore, the overall time complexity is approximately 9 * 2^(N-1). Which can be expressed as O(10 * 2^N) since the starting digits are limited by 10 and 2^(N-1) and 2^(N) are of the same exponential order.

Space Complexity

O(k * 10) – The algorithm uses a queue or list (implicit in steps 4 and 7 of the plain English explanation) to store the numbers being built. In the worst-case, for each possible starting digit (1-9, so at most 9), it explores at most k digits (where k is the desired length N), leading to roughly k * 9 possibilities stored. Since we are asked to consider single digit numbers as a starting point, we can assume that 0 is an acceptable start. This changes our amount of starting digits from 9 to 10 so that changes the amount of possiblities to k * 10, even though 0 cannot be a first digit. Therefore, the auxiliary space scales with the length of the desired numbers, k and a constant 10 representing the maximum number of starting digits.

Optimal Solution

Approach

The best way to solve this is to build the numbers one digit at a time, exploring all valid options at each step. This allows us to avoid generating numbers that don't meet the criteria early on, making the whole process much faster.

Here's how the algorithm would work step-by-step:

Start by figuring out all the possible single-digit numbers that we can begin with.
For each of those starting numbers, figure out what the next digit could be based on the given difference. It can be the previous digit plus the difference, or the previous digit minus the difference.
If adding or subtracting the difference results in a valid digit (0 to 9), add it to the number we're building.
Repeat this process of adding digits based on the difference until we have numbers of the required length.
Avoid adding the same number multiple times. For example, if difference is zero, avoid repeated numbers like 11 and 77.
Once you have a list of all the numbers that fit the rules, return that list.

Code Implementation

def numbers_with_same_consecutive_differences(number_length, difference):
    results = set()

    def generate_numbers(current_number, remaining_length):
        if remaining_length == 0:
            results.add(current_number)
            return

        last_digit = current_number % 10

        possible_next_digits = []
        if last_digit + difference <= 9:
            possible_next_digits.append(last_digit + difference)
        if last_digit - difference >= 0:
            possible_next_digits.append(last_digit - difference)

        for next_digit in possible_next_digits:
            generate_numbers(current_number * 10 + next_digit, remaining_length - 1)

    # Iterate through single digit numbers to start the sequence.
    for starting_digit in range(1, 10):
        generate_numbers(starting_digit, number_length - 1)

    # Remove leading zeros while maintaining uniqueness.
    final_results = sorted(list(results))
    return final_results

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible n-digit numbers that can be formed following the specified difference rule. In the worst case, each digit has two choices (adding or subtracting the difference), leading to a branching factor of 2 for each digit. Since we're building numbers of length n, this branching occurs n times. Therefore, in the worst-case scenario, the number of possible numbers explored grows exponentially with n, resulting in a time complexity of O(2^n).

Space Complexity

O(10 * 3^N) – The algorithm uses a recursive approach to build numbers of length N. In the worst case, for each of the 10 possible starting digits, each recursive call can potentially branch into up to two more calls (adding or subtracting the difference, though zero difference reduces this branching). This leads to a call tree where each level can have up to twice the number of calls as the previous level, leading to exponential space complexity with a base of 2. Additionally, a set is used to store the generated numbers to avoid duplicates. The maximum size of the set grows with the number of generated numbers, but storing the generated numbers grows exponentially so we can ignore the constant space of the set. Also the exponential branching can be limited, given the constraints of 0-9 digit values, and the fact that zero difference limits branching. The complexity can be seen as O(10*2^N) or more precisely O(10*3^N).

Edge Cases

Case	How to Handle
N is 0	Return an empty list as no digits can be formed.
K is larger than 9 or less than -9	If K is outside the valid digit difference range, the generator will produce an empty list or only single digit numbers if N is 1; otherwise it will produce no results.
N is a very large number (e.g., 10 or greater)	The recursive approach needs optimization to avoid excessive call stack depth which will lead to stack overflow errors; memoization might be an option.
K is 0	The solution should generate numbers with all identical digits.
N is 1	Return a list of digits from 0 to 9.
Leading zeros for N > 1 (e.g., '01', '02' are not valid)	Ensure that the first digit of the generated number is not zero unless N=1.
Integer overflow when constructing the number	Use a data type capable of holding larger numbers, such as `long` or perform checks to prevent overflow before appending digits; consider using string representation to handle numbers of large magnitude instead of int.
All numbers from 1 to 9, with all the same difference	The algorithm generates all possibilities based on the given K, so it will correctly handle this case.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for the digits `n` and `k`? Specifically, what are the maximum and minimum possible values for `n` and `k`?
Should I return the numbers with `n` digits as a list of integers or as a list of strings?
If `k` is 0, are consecutive digits allowed to be the same?
Should the output list be sorted in any particular order, such as ascending or descending?
Are leading zeros permitted in the generated numbers (e.g., if n=2, can '07' be considered a valid number)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with each single-digit number as a potential starting point.
For each potential number, try adding another digit at the end.
Check if the difference between the new digit and the last digit of the current number matches the allowed difference.
If it matches, keep the new, longer number and repeat the process of adding another digit.
If it doesn't match, discard that possibility and try a different digit.
Continue adding digits until the number reaches the required length.
If a number reaches the required length while still following the difference rule, save it.
Repeat this whole process starting from each possible single-digit number.
Finally, return all the saved numbers that satisfy the conditions.

Code Implementation

def numbers_with_same_consecutive_differences(number_length, difference):
    results = []

    # Iterate through single digit numbers as starting points
    for starting_digit in range(1, 10):
        def generate_numbers(current_number):
            if len(str(current_number)) == number_length:
                results.append(current_number)
                return

            last_digit = int(str(current_number)[-1])

            # Check possible next digits based on the difference
            possible_next_digits = [last_digit + difference, last_digit - difference]

            for next_digit in possible_next_digits:
                # Validate next digit to be from 0 to 9
                if 0 <= next_digit <= 9:
                    generate_numbers(current_number * 10 + next_digit)

        generate_numbers(starting_digit)

    # Remove duplicate numbers
    return list(set(results))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by figuring out all the possible single-digit numbers that we can begin with.
For each of those starting numbers, figure out what the next digit could be based on the given difference. It can be the previous digit plus the difference, or the previous digit minus the difference.
If adding or subtracting the difference results in a valid digit (0 to 9), add it to the number we're building.
Repeat this process of adding digits based on the difference until we have numbers of the required length.
Avoid adding the same number multiple times. For example, if difference is zero, avoid repeated numbers like 11 and 77.
Once you have a list of all the numbers that fit the rules, return that list.

Code Implementation

def numbers_with_same_consecutive_differences(number_length, difference):
    results = set()

    def generate_numbers(current_number, remaining_length):
        if remaining_length == 0:
            results.add(current_number)
            return

        last_digit = current_number % 10

        possible_next_digits = []
        if last_digit + difference <= 9:
            possible_next_digits.append(last_digit + difference)
        if last_digit - difference >= 0:
            possible_next_digits.append(last_digit - difference)

        for next_digit in possible_next_digits:
            generate_numbers(current_number * 10 + next_digit, remaining_length - 1)

    # Iterate through single digit numbers to start the sequence.
    for starting_digit in range(1, 10):
        generate_numbers(starting_digit, number_length - 1)

    # Remove leading zeros while maintaining uniqueness.
    final_results = sorted(list(results))
    return final_results

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
N is 0	Return an empty list as no digits can be formed.
K is larger than 9 or less than -9	If K is outside the valid digit difference range, the generator will produce an empty list or only single digit numbers if N is 1; otherwise it will produce no results.
N is a very large number (e.g., 10 or greater)	The recursive approach needs optimization to avoid excessive call stack depth which will lead to stack overflow errors; memoization might be an option.
K is 0	The solution should generate numbers with all identical digits.
N is 1	Return a list of digits from 0 to 9.
Leading zeros for N > 1 (e.g., '01', '02' are not valid)	Ensure that the first digit of the generated number is not zero unless N=1.
Integer overflow when constructing the number	Use a data type capable of holding larger numbers, such as `long` or perform checks to prevent overflow before appending digits; consider using string representation to handle numbers of large magnitude instead of int.
All numbers from 1 to 9, with all the same difference	The algorithm generates all possibilities based on the given K, so it will correctly handle this case.