# Separate Numbers ( University CodeSprint 2, Hackerrank )

A numeric string, \(s\) , is *beautiful* if it can be split into a sequence of two or more positive integers, \(a_1, a_2, …, a_n\), satisfying the following conditions:

- \( a_{i} – a_{i-1} = 1 \) for any \( 1 \lt i \le n\) (i.e., each element in the sequence is \( 1\) more than the previous element).
*No \(a_i\) contains a leading zero.*For example, we can split \(s = 10203\) into the sequence \( \{1, 02, 03\} \) , but it is*not*beautiful because \(02\) and \(03\) have leading zeroes.*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 \neq 1 \)) .

The diagram below depicts some beautiful strings:

You must perform queries, where each query consists of some string . For each query, print whether or not the string is beautiful on a new line. If it’s beautiful, print **
YES x**, where is the first number of the increasing sequence (if there are multiple such values of , choose the smallest); otherwise, print **
NO** instead. **Read Full Problem Statement**.

**Above problem can be solved using following approaches:**

Lets understand the problem statement once again. A string with some sequence of number is given and we are asked to determine whether this sequence has an **increasing sequence** or not. If YES then find the minimum number and print it along with YES.

**In order to solve this problem one has to answer following questions:**

**How to store the data****Which data structure to use****How to reduce complexity****What is prerequisite to solve this problem?**

**Let’s answer these questions one by one**

**1. How to store the data**

**Since it is mentioned that sequence of numbers are given hence a string will be helpful. One more important observation is that we need to use (long int). Why?? (we will discuss later)**

**2. Which Data Structure to use**

**As such no Data Structure required.**

**3. How to reduce complexity **

**After looking at constrains we can easily say brute force technique will work.**

**4. What is prerequisite to solve this problem?**

**Basic implementation, Observation.**

** ****Let’s begin with some sample example **

**Given \( s = 1234 \) h****ow many sequences are possible?**

\( \{ 1, 2, 3, 4 \} \) , \( \{ 12, 34 \} \)

Why not \( \{ 123, 4 \} \) **(think about it)**

Therefore a sequence will contain at least 2 numbers. Otherwise It’s a NO

**Remember a number must not begin with ‘0’ but following is a valid sequence**\( 1234 \).

Like in our 1^{st} point we found two sequences if both of them are not in increasing sequence then only solutions doesn’t exist. At each step we will extract one number starting from
length = 1 to n/2.

Len 1: \( \{ 1, 234 \} \) => \( 1 + 1 \) => \(2\) Now check existence of 2

Yes two is another number after extracting another number.

**Another question what will happen when a number like “910” is encountered.**

No need to worry because first we are extracting a number of length=1 then converting it to integer, incrementing it by 1 and again converting it to string. Here we will extract a number of size similar to this converted number.

Len 2: \( \{12, 34 \} \) => \( 12 + 1 \) => \(13\) No next number is not present.

Repeat steps until Length = n/2

If (no sequence exists)

Print NO

Else

Print “YES”

**Next question How to find Minimum number?**It’s the first number of length ‘Len’ that we have extracted initially….

**Have a look at following code for better understanding…**

#include<bits/stdc++.h> using namespace std; string conv_string(long long number) { return to_string(number); } long long conv_num(string T) { return atol(T.c_str()); } string S; int Siz; bool is_a_sequence(string T,int Index) { while(Index<Siz) { long long number = conv_num(T); number=number+1; string temp = conv_string(number); int s_index=Index; for(int i=0;i<temp.size();i++) { if(S[s_index++]!=temp[i]) return false; } T=temp; Index+=(T.size()); } if(Index==Siz) return true; return false; } int main() { int q; cin>>q; for(int i=0;i<q;i++) { cin>>S; Siz=S.size(); bool fl=false; long long First=0; int Len=1; while(Len<=Siz/2) { string temp; for(int i=0;i<Len;i++) temp+=S[i]; if(is_a_sequence(temp,Len)) { fl=true; First=conv_num(temp); break; } Len++; } fl?cout<<"YES "<<First:cout<<"NO"; cout<<endl; } return 0; }

This article is contributed by Ravi Kant. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.