In this post, we will solve Separate the Numbers HackerRank Solution. This problem (Separate the Numbers) is a part of HackerRank Problem Solving series.
Task
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 < i <= 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 != 1).
The diagram below depicts some beautiful strings:
Perform q queries where each query consists of some integer string s. For each query, print whether or not the string is beautiful on a new line. If it is 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
.
Function Description
Complete the separateNumbers function in the editor below.
separateNumbers has the following parameter:
- s: an integer value represented as a string
Prints
– string: Print a string as described above. Return nothing.
Input Format
The first line contains an integer q, the number of strings to evaluate.
Each of the next q lines contains an integer string s to query.
Constraints
- 1 <= q <= 10
- 1 <= |s| <= 32
- s[i] ∈ [0 – 9]
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.
Sample Input 1
4
99910001001
7891011
9899100
999100010001
Sample Output 1
YES 999
YES 7
YES 98
NO
Solution – Separate the Numbers – HackerRank Solution
C++
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; bool check(string str,int ind ,long long int prev){ if(ind == str.size() -1 && prev - (str[ind] -'0') == -1){ return true; } else if(ind == str.size() ) return true; long long int k=0; int i; for(i =ind; i < str.size(); i++){ k = k *10 + (str[i]-'0'); if(prev-k == -1){ if( i+ 1 == str.size()){ return true; } return check(str,i+1, k); } else if(k - prev > 1) { return false; } } return false; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n; cin >>n; while(n--){ string str; int k; cin >>str; //cout<< str <<" i " << n <<endl; if(str[0] == '0' || str.size() <=1){ cout << "NO"<<endl; continue; } long long int j=0; bool f =false; for(k =0; k<str.size()-1; k++){ j = j*10 +str[k]-'0'; f = check(str,k+1,j); if(f ==true){ //cout << k <<" "<<str <<endl; cout <<"YES"<< " " << j <<endl; break; } } if(f== false) cout <<"NO" <<endl; } return 0; }
Python
#!/bin/python3 import sys def validate(s, first): while s: if s.startswith(first): s = s[len(first):] first = str(int(first) + 1) else: return False return True def separateNumbers(s): if s[0] == '0' and len(s) > 1: return "NO" else: for ind in range(1, len(s)//2 + 1): first = s[:ind] if validate(str(s), first): return "YES " + first return "NO" if __name__ == "__main__": q = int(input().strip()) for a0 in range(q): s = input().strip() print(separateNumbers(s))
Java
import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int q = sc.nextInt(); for (int tc = 0; tc < q; tc++) { String s = sc.next(); long result = solve(s); System.out.println(result > 0 ? "YES " + result : "NO"); } sc.close(); } static long solve(String s) { if (s.charAt(0) == '0') { return -1; } for (int length = 1; length * 2 <= s.length(); length++) { long firstNumber = Long.parseLong(s.substring(0, length)); StringBuilder sequence = new StringBuilder(); long number = firstNumber; while (sequence.length() < s.length()) { sequence.append(number); number++; } if (sequence.toString().equals(s)) { return firstNumber; } } return -1; } }
Note: This problem (Separate the Numbers) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.