Given a numeric string, the task is to split the string into the sequence of two or more positive integers and check that it satisfies the following conditions or not.
1. Each element in the sequence is 1 more than the previous element. for example, a[1]-a[0] = 1.
2. None of the sequences of a string having leading zero. for example, we can split a string s = 102030405 into sequence {1, 02, 03, 04, 05}, 02, 03, 04, and 05 having leading zeroes.
3. The sequence of the string cannot be rearranged. For example, we can split a string s = 11910 into the sequence {11, 9, 10}, it breaks our first condition (i.e. 9-11 = -2, so it doesn’t equal to 1)
If it satisfies the following conditions print “YES” X, where X is the first number of the increasing sequence, Otherwise print “NO”.
Examples :
Input : String s = 123456
Output : YES 1
Explanation :
For s = 123456, we can split s = 123456 into the sequence
{1, 2, 3, 4, 5, 6}, (i.e. 2-1 = 1, 3-2 = 1, 4-3 = 1, and so on) that
satisfy all the conditions.
Input : String s = 9101112
Output : YES 9
Explanation :
For s = 9101112, we can split s = 9101112 into the sequence
{9, 10, 11, 12}, (i.e. 10-9 = 1, 11-10 = 1, and so on) that satisfy
all the conditions.
Input : String s = 15
Output : NO
Explanation :
For s = 15, the only possible sequence is {1, 5} which violate the
first condition.
Input : String s = 102030405
Output : NO
Explanation :
For s = 102030405, it starts with a zero so all possible splits
violate the second condition.
Approach :
1. Check every possible substring(number) of different lengths, up to the mid-length of the input string.
2. Set the substring(number) you’re working on as the first element of your sequence.
3. Save your substring(number) starting sequence so you can use it later.
4. Set the same substring(number) as a valid string.
5. Increment the first valid string and add it to the valid string you just created. You will start building a string like “9”, “910”, “91011”, “9101112”.
6. Stop doing this once your valid string length exceeds the length of the input string.
7. Compare the valid string you created is equal to the input string, If it is true, print “YES”. If not, go to step 2 and try with a new incremented substring that is one digit longer.
Implementation :
// Java program to split the string into
// the sequence of two or more positive integers
class Main{
// function to split the string.
static void separateNumbers(String s){
String substring = "";
boolean isValid = false;
// traverse the string up to mid-length of the input string
for(int i = 1; i <= s.length()/2; i++){
// find the substring
substring = s.substring(0, i);
// convert the string into number
Long num = Long.parseLong(substring);
String validString = substring;
// Increment the first valid string and
// add it to the valid string you just created.
// Stop doing this once your valid string length
// exceeds the length of the input string
while(validString.length() < s.length()){
validString += Long.toString(++num);
}
// Compare the valid string with the input string.
if(s.equals(validString)){
isValid = true;
break;
}
}
System.out.println(isValid ? "YES " + substring : "NO");
}
// Driver Code
public static void main(String args[]){
//Test Case 1:
String s1 = "123456";
separateNumbers(s1);
//Test Case 2:
String s2 = "9101112";
separateNumbers(s2);
//Test Case 3:
String s3 = "15";
separateNumbers(s3);
//Test Case 4:
String s4 = "102030405";
separateNumbers(s4);
}
}
Output :
YES 1 YES 9 NO NO
