Leetcode 967. Numbers With Same Consecutive Differences

  • Solution 1

Logic: BFS level by level, the previous level is diffrent from other level by the length, DP for state transformation. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Java:
public int[] numsSameConsecDiff(int N, int K) {
        List<Integer> cur = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
        for (int i = 2; i <= N; ++i) {
            List<Integer> cur2 = new ArrayList<>();
            for (int x : cur) {
                int y = x % 10;
                if (x > 0 && y + K < 10)
                    cur2.add(x * 10 + y + K);
                if (x > 0 && K > 0 && y - K >= 0)
                    cur2.add(x * 10 + y - K);
            }
            cur = cur2;
        }
        return cur.stream().mapToInt(j->j).toArray();
    }

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> numsSameConsecDiff(int N, int K) {
        vector<int> cur = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
        for (int i = 2; i <= N; ++i) {
            vector<int> cur2;
            for (int x : cur) {
                int y = x % 10;
                if (x > 0 && y + K < 10)
                    cur2.push_back(x * 10 + y + K);
                if (x > 0 && K > 0 && y - K >= 0)
                    cur2.push_back(x * 10 + y - K);
            }
            cur = cur2;
        }
        return cur;
    }

  • Solution 2: dfs find the path to construct a number and until all the number is added.

Below are two different coding style for DFS. The point is that which one is more efficiency.
In C++ solution, it start from 1 to 9, and the dfs path is directly find the num+K or num-K, as goes further.
the Java solution start from the 0 case, and dfs by 0 to 9 check every possible case.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> numsSameConsecDiff(int N, int K){
	//base case from 1
	if(N==1) return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	vector<int> res;
	//from 1 ... dfs, because 0 can not be in the front
	for(auto num = 1; num <= 9; ++num){
		dfs(num, N-1, K, res);
	}
	return res;
}

//dfs method
void dfs(int num, int N, int K, vector<int> &res){
	//terinal cases
	if(N==0) res.push_back(num);
	else{
		//two path to find the final possible number
		if(num%10 + K<=9) dfs(num*10 + num%10 + K, N-1, K, res);
		if(nums10 -K >= 0) dfs(nums*10 + num%10 -K, N-1, K, res);
	}
}
Java
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
public int[] numsSameConsecDiff(int N, int K) {
        List<Integer> list = new ArrayList<>();
        if(N==0)
            return new int[0];
        if(N==1)
			list.add(0);      // edge case
        dfs(N, K, list, 0);
        return list.stream().mapToInt(i->i).toArray();   //list.toArray(new int[list.size()]); doesn't work for primitives
    }
    public void dfs(int N, int K, List<Integer> list, int number){
        if(N == 0){   // base case, if you have added enough number of integers then append it to list; Here N is used as the total digits in temporary number 
            list.add(number);
            return ;
        }
        for(int i=0; i<10; ++i){
            if(i==0 && number ==0)    // Do not add 0 at begining of a number
                continue;
            else if(number == 0 && i!=0){     // base case, we add all the digits when we do not have any previous digit to check if difference = K
                dfs(N-1, K, list, i);
            }
            else{
                if(Math.abs((number%10) - i )==K){
                    dfs(N-1, K, list, number*10+i);    // General dfs to add the digit at the units place and reducing the number of digits by 1.
                }
            }
        }
    }