Skip to content

967. Numbers With Same Consecutive Differences 👍

  • Time: $O(n \cdot 2^n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  vector<int> numsSameConsecDiff(int n, int k) {
    if (n == 1)
      return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    vector<int> ans;

    if (k == 0) {
      for (char c = '1'; c <= '9'; ++c)
        ans.push_back(stoi(string(n, c)));
      return ans;
    }

    for (int num = 1; num <= 9; ++num)
      dfs(n - 1, k, num, ans);

    return ans;
  }

 private:
  void dfs(int n, int k, int num, vector<int>& ans) {
    if (n == 0) {
      ans.push_back(num);
      return;
    }

    const int lastDigit = num % 10;

    for (const int nextDigit : {lastDigit - k, lastDigit + k})
      if (0 <= nextDigit && nextDigit <= 9)
        dfs(n - 1, k, num * 10 + nextDigit, ans);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  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 ArrayList<>();

    if (k == 0) {
      for (char c = '1'; c <= '9'; ++c) {
        final String s = String.valueOf(c).repeat(n);
        ans.add(Integer.parseInt(s));
      }
      return ans.stream().mapToInt(Integer::intValue).toArray();
    }

    for (int num = 1; num <= 9; ++num)
      dfs(n - 1, k, num, ans);

    return ans.stream().mapToInt(Integer::intValue).toArray();
  }

  private void dfs(int n, int k, int num, List<Integer> ans) {
    if (n == 0) {
      ans.add(num);
      return;
    }

    final int lastDigit = num % 10;

    for (final int nextDigit : new int[] {lastDigit - k, lastDigit + k})
      if (0 <= nextDigit && nextDigit <= 9)
        dfs(n - 1, k, num * 10 + nextDigit, ans);
  }
}