Separate the Numbers

Separate the Numbers

Problem Link: Separate the Numbers

A numeric string, s, is beautiful if it can be split into a sequence of two or more positive integers, a1,a2,….. ,an, satisfying the following conditions:

1. ai-ai-1 = 1 for any 1≤ i≤ n (i.e., each element in the sequence is 1 more than the previous element).
2. No ai contains a leading zero. For example, we can split s = 10203 into {1, 02, 03 } the sequence , 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 {3, 1, 2}, but it is not beautiful because it breaks our first constraint (i.e., 1–3 ≠ 1 ).

The diagram below depicts some beautiful strings:

You must perform q queries, where each query consists of some s string . 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 q (the number of strings to evaluate).
Each of the q subsequent lines contains some s string for a query.

Constraints
1 ≤ q ≤ 10
1 ≤ |s| ≤ 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 {1,3}, which violates the first condition.
• For s=1, there are no possible splits because s only has one digit.

SOLUTION

My approach here is Brute Force, simply check for the number for the different number of digits sequence starting from 1 to half of length of the string. If at any point the condition failed which is that next number must be consecutive we will break the loop and check for the next digits value.

Let’s take an example 101102103
First we will check for dig =1
And when the second iteration come which will give us 0 which is not consecutive to 1 we wil lbreak here
Now for dig = 2
The first number will be 10
Second will be 11
But at third iteration it will be 02 which is not next to 11 so we will break here
Now for dig = 3
The first number we will get is 101 and then 102 and then 103
Now our string will end so we break from here.

Now points to be noted while coding above approach is
No leading zero are allowed, so we need to check this for the first digit only if the number formed by the dig and the number formed don’t have the same number of digits it will not be our answer

Now we have to check for the next number also if 9,99,999 will come so we will increase our temporary digit count by one.

See the code for a better explanation.

CODE

#include<iostream>
#include<string>
using namespace std;
#define ll long long
//A FUNCTION TO CHECK LEADING ZERO
// LOGIC IS SIMPLE NUMBER OF DIGIT IN THE NUMBER FORMED MUST BE EQUAL TO THE NUMBER OF THE DIGIT WE ARE RUNNING LOOP FOR
bool checkLeadingZero(ll next_num,ll temp_dig)
{
 ll count=0;
 while(next_num) {
 count++;
 next_num/=10;
 }
 return count==temp_dig;
}
int main()
{
 ll q; cin>>q;
 while(q--)
 {
 string s; cin>>s;
 ll len = s.length();
 bool flag = false;
 ll firstNum=0;
 for(ll dig=1;dig<=len/2;dig++) // loop for each length
 {
 ll max =0; //setting max for each digit number
 for(ll i=1;i<=dig;i++) // CALCULATING MAX
 max = max*10+9;
 ll temp_dig = dig; //setting temp digit as we have to increase the digit if we found that number reaches to max
firstNum = 0;
 for(ll i=0;i<dig;i++)
 firstNum = firstNum*10 + (s[i]-'0'); // forming the number as input is the string
if(checkLeadingZero(firstNum,dig)==false)
 {
 flag=false;
 break;
 }
 ll j=dig;
 ll currentNum = firstNum; //setting current
while(1)
 {
 if(j == len){
 flag = true;
 break;
 }
 if(currentNum == max) temp_dig++;
 ll next_num =0;
 if(j+temp_dig > len)
 break;
 for(int i=j;i<j+temp_dig;i++) // forming next number 
 next_num = next_num*10 + (s[i]-'0');
if(next_num - currentNum!=1)
 break;
 else
 {
 currentNum=next_num;
 j = j+temp_dig;
 }
 }
 if(flag==true) break;
 }
 if(flag==true) cout<<"YES "<<firstNum<<endl;
 else cout<<"NO"<<endl;
 }
}