Algorithm


Problem Name: 967. Numbers With Same Consecutive Differences

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

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int[] numsSameConsecDiff(int n, int k) {
    List result = new ArrayList<>();
    helper(n, k, result, new StringBuilder());
    return result.stream().mapToInt(Integer::intValue).toArray();
  }

  private void helper(int n, int k, List < Integer> result, StringBuilder sb) {
    if (sb.length() == n) {
      result.add(Integer.parseInt(sb.toString()));
      return;
    }
    for (int i = 0; i  < = 9; i++) {
      if (sb.isEmpty() && i == 0) {
        continue;
      }
      if (!sb.isEmpty()
          && Math.abs(Character.getNumericValue(sb.charAt(sb.length() - 1)) - i) != k) {
        continue;
      }
      sb.append(i);
      helper(n, k, result, new StringBuilder(sb));
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 3, k = 7

Output

x
+
cmd
[181,292,707,818,929]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const numsSameConsecDiff = function (n, k) {
  const res = []
  
  for(let i = 1; i  < = 9; i++) {
    dfs(n - 1, [i])
  }
 
  return res

  function dfs(num, arr) {
    if(num === 0) {
      res.push(+arr.join(''))
      return 
    }

    for(let i = 0; i <= 9; i++) {
      if(Math.abs(i - arr[arr.length - 1]) === k) {
        arr.push(i)
        dfs(num - 1, arr)
        arr.pop(>
      }
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 3, k = 7

Output

x
+
cmd
[181,292,707,818,929]

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        q = {i for i in range(10)}
        for _ in range(N - 1):
            new = set()
            for num in q:
                last = num % 10
                if num and 0 <= last + K <= 9:
                    new.add(num * 10 + last + K)
                if num and 0 <= last - K <= 9:
                    new.add(num * 10 + last - K)
            q = new
        return list(q)
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 2, k = 1

Output

x
+
cmd
[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

#4 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0967_NumbersWithSameConsecutiveDifferences
    {
        public int[] NumsSameConsecDiff(int N, int K)
        {
            var resutls = new List < int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            for (int i = 2; i  < = N; i++)
            {
                var temp = new List<int>();
                foreach (var num in resutls)
                {
                    var digit = num % 10;
                    if (num > 0 && K > 0 && digit - K >= 0)
                        temp.Add(num * 10 + digit - K);
                    if (num > 0 && digit + K  <  10)
                        temp.Add(num * 10 + digit + K);
                }
                resutls = temp;
            }
            return resutls.ToArray();
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 2, k = 1

Output

x
+
cmd
[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
Advertisements

Demonstration


Previous
#966 Leetcode Vowel Spellchecker Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#968 Leetcode Binary Tree Cameras Solution in C, C++, Java, JavaScript, Python, C# Leetcode