DEV Community

Cover image for LeetCode Daily Problem - 967. Numbers With Same Consecutive Differences
Upamanyu Das
Upamanyu Das

Posted on

1 1

LeetCode Daily Problem - 967. Numbers With Same Consecutive Differences

Problem

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.

Idea

The way to solve this is to construct the number digit by digit. We can pick any digit x from 1 through 9 as the first digit. Once we have picked the digit we have at most two valid choices x + k and x - k i.e. they both lie in [0, 9]. The problem then reduces to solving a smaller problem with similar structure, i.e. with one less digit at every step. When n digits have been picked we can add the number to our answer array.

Solution

class Solution {
    public void dfs (int NumOfDigits, int currNum, int k, List<Integer> ans) {
        if (NumOfDigits == 0) {
            ans.add(currNum);
            return;
        }

        List<Integer> nextDigits = new ArrayList<>();

        int tailDigit = currNum % 10;
        nextDigits.add(tailDigit + k);
        if(k != 0) {
            nextDigits.add(tailDigit - k);
        }

        for(int nextDigit : nextDigits) {
            if(0 <= nextDigit && nextDigit < 10) {
                int num = currNum * 10 + nextDigit;
                dfs(NumOfDigits - 1, num, k, ans);
            }
        }
    }

    public int[] numsSameConsecDiff(int n, int k) {
        if (n == 1) {
            return new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        }

        List<Integer> ans = new LinkedList<Integer>();

        for (int i = 1; i < 10; i++) {
            dfs(n - 1, i, k, ans);
        }

        return ans.stream().mapToInt(i -> i).toArray();

    }
}
Enter fullscreen mode Exit fullscreen mode

Runtime: 9 ms, faster than 21.14% of Java online submissions for Numbers With Same Consecutive Differences.

Memory Usage: 44.2 MB, less than 6.62% of Java online submissions for Numbers With Same Consecutive Differences.

Note - The BFS solution of this problem will be much more memory efficient as the recursion stack will not have to be dealt with.

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay