Consecutively Descending Integers Editorial

Practice Problem Link: Consecutively Descending Integers

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string containing digits, determine if the string can be broken into consecutively descending integers.

Approach

We will try to make a number with all the possible lengths of prefixes, and then use that number as the starting point of the descending series to check if it is possible to make a consecutively descending series starting with that number. If any of the prefixes becomes a possible valid series, then return true, else return false.

Analysis

• Time Complexity: O(2ⁿ)
• Space Complexity: O(2ⁿ)

Implementation

C++

vector<int> possibleList;
bool isPossible;
void solve(string c,int start,int n){
	if(start == n) {
		for(int i = 1; i < possibleList.size(); i++) {
			if(possibleList[i - 1] - 1 == possibleList[i]) {
				continue;
			}
			isPossible = false;
			return;
		}
		if(possibleList.size() != 1) {
			isPossible = true;
		}
		return;
	}

	int num = 0;
	for(int i = start; i < n; i++){
		num = num * 10 + (c[i] - '0');
		possibleList.push_back(num);
		solve(c, i + 1, n);
		if(isPossible){
			return;
		}
		possibleList.pop_back();
	}
}
bool isConsecutivelyDescending(string s) {
	possibleList.clear();
	isPossible = false;
	solve(s, 0, s.length());
	return isPossible;
}

Java

class Solution {
	ArrayList<Integer> possibleList;
	boolean isPossible;
	void solve(char c[],int start,int n){
		if(start == n) {
			for(int i = 1; i < possibleList.size(); i++) {
				if(possibleList.get(i - 1) - 1 == possibleList.get(i)) {
					continue;
				}
				isPossible = false;
				return;
			}
			if(possibleList.size() != 1) {
				isPossible = true;
			}
			return;
		}
		
		int num = 0;
		for(int i = start; i < n; i++){
			num = num * 10 + (c[i] - '0');
			possibleList.add(num);
			solve(c, i + 1, n);
			if(isPossible == true){
				return;
			}
			possibleList.remove(possibleList.size() - 1);
		}
	}
	boolean isConsecutivelyDescending(String s) {
		possibleList = new ArrayList<>();
		isPossible = false;
		solve(s.toCharArray(), 0, s.length());
		return isPossible;
	}
}