## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Separate the numbers challenge

Sharing is caring!

Problem statement
A numeric string, $s$, is beautiful if it can be split into a sequence of two or more positive integers, $1_1, a_2, \dots, a_n$, satisfying the following conditions:

1. $a_i - a_{i-1} = 1$ for any $1 \textless i \le n$ (i.e., each element in the sequence is $1$ more than the previous element).
2. No $a_i$ contains a leading zero. For example, we can split $s=10203$ into the sequence $\left[1, 02, 03\right]$, but it is not beautiful because $02$ and $03$ have leading zeroes.
3. The contents of the sequence cannot be rearranged. For example, we can split $s=312$ into the sequence $\left[3, 1, 2\right]$, but it is not beautiful because it breaks our first constraint (i.e., $1 - 3 \ne 1$).

The diagram below depicts some beautiful strings: You must perform $q$ queries, where each query consists of some string $s$. For each query, print whether or not the string is beautiful on a new line. If it’s beautiful, print YES x, where $x$ is the first number of the increasing sequence (if there are multiple such values of $x$, choose the smallest); otherwise, print NO instead.

Input Format
The first line contains an integer denoting (the number of strings to evaluate).
Each of the subsequent lines contains some string for a query.

Constraints $1 \le q \le 10$ $1 \le |s| \le 32$
Each character in $s$ is a decimal digit from $0$ to $9$ (inclusive).

Output Format
For each query, print its answer on a new line (i.e., either YES x where $x$ is the smallest first number of the increasing sequence, or NO).

Sample Input 0

7
1234
91011
99100
101103
010203
13
1


Sample Output 0

YES 1
YES 9
YES 99
NO
NO
NO
NO


Explanation 0
The first three numbers are beautiful (see the diagram above). The remaining numbers are not beautiful:

For $s = 101103$, all possible splits violate the first and/or second conditions.
For $s = 010203$, it starts with a zero so all possible splits violate the second condition.
For $s = 13$, the only possible split is $\left[1,3\right]$, which violates the first condition.
For $s = 1$, there are no possible splits because $s$ only has one digit.

Solution

public class SeparateTheNumbers {

/**
* Convert String to int
*/
private static long strToLong(String str) {
long ans = 0;

double d = str.length() - 1;
for (int i = 0; i < str.length(); i++) {
long digit = (long) (str.charAt(i) - '0');
if (digit != 0l) {
long pow = (long) Math.pow(10, d);
ans += digit * pow;
}
d--;
}

return ans;
}

private static long solve(String str, int startIdx, long prevNum, long diff) {
if (str.length() == 1) {
return -1;
}

if (startIdx == str.length() && diff == 1) {
return prevNum;
} else {

if (startIdx == str.length() || str.charAt(startIdx) == '0') {
return -1;
}

for (int len = 1; len <= str.length() - startIdx; len++) {
String nextSubStr = str.substring(startIdx, startIdx + len);
long next = strToLong(nextSubStr);

long result = -1;
if (next - prevNum == 1 || startIdx == 0) {
result = solve(str, startIdx + len, next, next - prevNum);
}

if (result > 0) {
return next;
}
}

return -1;
}
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);
int queries = in.nextInt();

for (int q = 0; q < queries; q++) {
String str = in.next();
long res = solve(str, 0, 0, 0);
System.out.println(res > 0 ? "YES " + res : "NO");
}
}

}