967. Numbers With Same Consecutive Differences

Numbers With Same Consecutive Differences

Problem 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

Approach) Brute Force

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function (n, k) {
  let nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];

  for (let len = 1; len < n; len++) {
    const newNums = [];
    for (const num of nums) {
      const remainder = num % 10;
	  
      const incNum = remainder + k;
      if (incNum >= 0 && incNum <= 9) {
        newNums.push(num * 10 + incNum);
      }

      const decNum = remainder - k;
      if (decNum >= 0 && decNum <= 9 && incNum !== decNum) {
        newNums.push(num * 10 + decNum);
      }
    }

    nums = newNums;
  }

  return nums;
};

Approach) Dynamic Programming

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function(n, k) {
    let list = [1, 2, 3, 4, 5, 6, 7, 8, 9]; // integers list
    while(--n > 0){
        let tmp = [];
        for(let val of list){
            let rem = val % 10;
            if(rem + k < 10){    // map digit by digit
                tmp.push(val * 10 + rem + k);
            }
            if(k != 0 && rem - k >= 0)  { // map digit by digit
                tmp.push(val * 10 + rem - k)
            }
        }
        list = tmp;
    }
    return list
};

OR

var numsSameConsecDiff = function(N, K) {
    let prevSet = new Set([0,1,2,3,4,5,6,7,8,9]);
    
    for (let n = 2; n <= N; n++) { // we start at 2 since n = 1 is just the one digit numbers 0 through 9
        const newSet = new Set();
        
        for (const prevVal of prevSet) {
            const lastDig = prevVal % 10;
            
            const plusK = lastDig + K;
            const minusK = lastDig - K;
            
            if (prevVal > 0 && plusK < 10) newSet.add((prevVal * 10) + plusK);
            if (prevVal > 0 && minusK >= 0) newSet.add((prevVal * 10) + minusK);
        }
        
        prevSet = newSet;
    }

    return [...prevSet];
};

Approach) Recursion

var numsSameConsecDiff = function (N, K) {
    let ret = new Set();

    let numsSameConsecDiffRec = (tmp) => {
        if (tmp.length == N) {
            let skip = tmp.length > 1 && tmp[0] == '0';
            if (!skip) ret.add(Number(tmp.join("")));
            return;
        }

        let last = tmp[tmp.length - 1];
        if (last - K >= 0) numsSameConsecDiffRec([...tmp, last - K]);
        if (last + K <= 9) numsSameConsecDiffRec([...tmp, last + K]);
    }

    for (let i = 0; i <= 9; i++) numsSameConsecDiffRec([i]);

    return [...ret];
};

Approach) Depth First Search

const numsSameConsecDiff = (N, K, ans = []) => {
    if (N === 1) return [0,1,2,3,4,5,6,7,8,9];   //Edge case: the only one where '0' qualifies
    const DFS = strnum => {                      //given some string representing a number strnum, build the string further using digits 0-9 in a way that the string satisfies the K difference rule
        if (strnum.length === N){                //if length N is reached, add to ans if not previously encountered
            const num = parseInt(strnum);
            if (!ans.includes(num)) ans.push(num);
            return;
        }
        const lastdigit = parseInt(strnum.slice(-1));
        if (lastdigit + K <= 9) DFS(strnum+(lastdigit+K).toString());   //continue building the number string until length = N using the two options that satisfy the K difference rule
        if (lastdigit - K >= 0) DFS(strnum+(lastdigit-K).toString());
        return;
    }
    for (let i = 1; i <= 9; i++) DFS(i.toString());  //Launch DFS off of all possible first digits (zero is not one, but the extension DFS function accounts for possibility of zero usage in the middle or on the end)
    return ans;
};

Approach) Depth First Search / BackTracking

let n, k, res;
const numsSameConsecDiff = (N, K) => {
    n = N;
    k = K;
    res = new Set();
    dfs('');
    return [...res];
};

const dfs = (cur) => {
    if (cur.length > n) return;
    if (cur.length == n && ok(cur)) res.add(cur);
    let start = cur.length == 0 ? 1: 0;
    for (let i = start; i < 10; i++) { // build '0-9' string
        cur += i + '';
        if (ok(cur)) { // ok, dfs further
            dfs(cur);
            cur = cur.slice(0, -1); // backtracking, withdraw last digit
        } else {
            cur = cur.slice(0, -1); // not ok, no need to dfs further, but change last digit and continue 
        }
    }
};

const ok = (s) => { // check consective absolute difference is all same
    if (s.length == 1) return true;
    if (s[0] == '0') return false;
    let n = s.length, diff = Math.abs((s[1] - '0') - (s[0] - '0'));
    if (diff != k) return false;
    for (let i = 2; i < n; i++) {
        let d = Math.abs((s[i] - '0') - (s[i - 1] - '0'));
        if (d != k) return false;
    }
    return true;
};

Approach) Binary Solution

1. I assume there will be 2^(N-1) maximum cases
2. I make map of all N-1 length numbers in 2 base systems: for example, for N=3, [[0,0],[1,0],[0,1],[1,1] is the map;
3. in the map, 0 means '+', 1 means '-'.
4. for each digit from 1 to 9, I put the cases and checked each element is in [0,9] or not

var numsSameConsecDiff = function(N, K) {
    let b=Array.apply(null, Array(N-1)).map(function(){return 0}); // set all elements to 0
    
    let a = [];
    a.push(b);
    for(let i=1;i<=Math.pow(2,N-1);i++) {
        let q=1; let c=[];  // add one to create new value of map
        for(let j=0;j<N-1; j++) {
          let sum = b[j]+q;
          c.push(Math.ceil(sum%2)); 
          q = Math.floor(sum/2);
        }
        b=c;
        a.push(c);
    }
 
    let ans=[];
    for(let s=1;s<10;s++) {  // [1,9] starting digits
        for(let i=1;i<=Math.pow(2,N-1);i++) {
            let valid=true;
            b = [s];c=''+s;
            for(let j=1;j<N; j++) {
                if(a[i][j-1]==0) { // choosing operators
                    b[j]=b[j-1]+K;
                }
                else {
                    b[j]=b[j-1]-K;
                }
                if(b[j]<0||b[j]>9) { 
                    valid=false;
                    break;
                }
                c+=''+b[j];
            }
            if(valid) {
                if(ans.indexOf(Number(c))==-1)ans.push(Number(c));
            }
        }
    }
    return ans;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #967. Numbers With Same Consecutive Differences

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!