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");
        }
    }

}