Welcome to Subscribe On Youtube

967. Numbers With Same Consecutive Differences

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.

 

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

Solutions

DFS.

  • class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < 10; ++i) {
            dfs(n - 1, k, i, res);
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); ++i) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    private void dfs(int n, int k, int t, List<Integer> res) {
        if (n == 0) {
            res.add(t);
            return;
        }
        int last = t % 10;
        if (last + k <= 9) {
            dfs(n - 1, k, t * 10 + last + k, res);
        }
        if (last - k >= 0 && k != 0) {
            dfs(n - 1, k, t * 10 + last - k, res);
        }
    }
}

  • class Solution {
public:
    vector<int> ans;

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

    void dfs(int n, int k, int t) {
        if (n == 0) {
            ans.push_back(t);
            return;
        }
        int last = t % 10;
        if (last + k <= 9) dfs(n - 1, k, t * 10 + last + k);
        if (last - k >= 0 && k != 0) dfs(n - 1, k, t * 10 + last - k);
    }
};

  • class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        ans = []

        def dfs(n, k, t):
            if n == 0:
                ans.append(t)
                return
            last = t % 10
            if last + k <= 9:
                dfs(n - 1, k, t * 10 + last + k)
            if last - k >= 0 and k != 0:
                dfs(n - 1, k, t * 10 + last - k)

        for i in range(1, 10):
            dfs(n - 1, k, i)
        return ans


  • func numsSameConsecDiff(n int, k int) []int {
	var ans []int
	var dfs func(n, k, t int)
	dfs = func(n, k, t int) {
		if n == 0 {
			ans = append(ans, t)
			return
		}
		last := t % 10
		if last+k <= 9 {
			dfs(n-1, k, t*10+last+k)
		}
		if last-k >= 0 && k != 0 {
			dfs(n-1, k, t*10+last-k)
		}
	}

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

  • function numsSameConsecDiff(n: number, k: number): number[] {
    const ans = new Set<number>();
    const boundary = 10 ** (n - 1);

    const dfs = (nums: number) => {
        if (nums >= boundary) {
            ans.add(nums);
            return;
        }

        const num = nums % 10;
        for (const x of [num + k, num - k]) {
            if (0 <= x && x < 10) {
                dfs(nums * 10 + x);
            }
        }
    };

    for (let i = 1; i < 10; i++) {
        dfs(i);
    }

    return [...ans];
}


  • function numsSameConsecDiff(n, k) {
    const ans = new Set();
    const boundary = 10 ** (n - 1);

    const dfs = nums => {
        if (nums >= boundary) {
            ans.add(nums);
            return;
        }

        const num = nums % 10;
        for (const x of [num + k, num - k]) {
            if (0 <= x && x < 10) {
                dfs(nums * 10 + x);
            }
        }
    };

    for (let i = 1; i < 10; i++) {
        dfs(i);
    }

    return [...ans];
}

All Problems

All Solutions