Dada una string numérica (longitud <= 32), divídala en dos o más enteros (si es posible), de modo que
1) La diferencia entre el número actual y el anterior sea 1.
2) Ningún número contiene ceros a la izquierda
Si es posible separar un string numérica dada, luego imprima » Posible » seguido del primer número de la secuencia creciente, de lo contrario imprima » No posible «.
Ejemplos:
Input : 1234 Output : Possible 1 Explanation: String can be split as "1", "2", "3", "4" Input : 99100 Output :Possible 99 Explanation: String can be split as "99", "100" Input : 101103 Output : Not Possible Explanation: It is not possible to split this string under given constraint.
Enfoque: la idea es tomar una substring del índice 0 a cualquier índice i (i comenzando desde 1) de la string numérica y convertirla en un tipo de datos largo. Súmale 1 y vuelve a convertir el número aumentado en una string. Compruebe si la siguiente substring que aparece es igual a la incrementada. En caso afirmativo, continúe con el procedimiento; de lo contrario, aumente el valor de i y repita los pasos.
C++
// C++ program to split a numeric
// string in an Increasing
// sequence if possible
#include <bits/stdc++.h>
using namespace std;
// Function accepts a string and
// checks if string can be split.
void split(string str)
{
int len = str.length();
// if there is only 1 number
// in the string then
// it is not possible to split it
if (len == 1) {
cout << ("Not Possible");
return;
}
string s1 = "", s2 = "";
long num1, num2;
for (int i = 0; i <= len / 2; i++) {
int flag = 0;
// storing the substring from
// 0 to i+1 to form initial
// number of the increasing sequence
s1 = str.substr(0, i + 1);
num1 = stoi((s1));
num2 = num1 + 1;
// convert string to integer
// and add 1 and again convert
// back to string s2
s2 = to_string(num2);
int k = i + 1;
while (flag == 0) {
int l = s2.length();
// if s2 is not a substring
// of number than not possible
if (k + l > len) {
flag = 1;
break;
}
// if s2 is the next substring
// of the numeric string
if ((str.substr(k, k + l) == s2)) {
flag = 0;
// Increase num2 by 1 i.e the
// next number to be looked for
num2++;
k = k + l;
// check if string is fully
// traversed then break
if (k == len)
break;
s2 = to_string(num2);
l = s2.length();
if (k + 1 > len) {
// If next string doesnot occurs
// in a given numeric string
// then it is not possible
flag = 1;
break;
}
}
else
flag = 1;
}
// if the string was fully traversed
// and conditions were satisfied
if (flag == 0) {
cout << "Possible " << s1 << endl;
break;
}
// if conditions failed to hold
else if (flag == 1 && i > len / 2 - 1) {
cout << "Not Possible" << endl;
break;
}
}
}
// Driver code
int main()
{
string str = "99100";
// Call the split function
// for splitting the string
split(str);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to split a numeric
// string in an Increasing
// sequence if possible
import java.io.*;
import java.util.*;
class GFG {
// Function accepts a string and
// checks if string can be split.
public static void split(String str)
{
int len = str.length();
// if there is only 1 number
// in the string then
// it is not possible to split it
if (len == 1) {
System.out.println("Not Possible");
return;
}
String s1 = "", s2 = "";
long num1, num2;
for (int i = 0; i <= len / 2; i++) {
int flag = 0;
// storing the substring from
// 0 to i+1 to form initial
// number of the increasing sequence
s1 = str.substring(0, i + 1);
num1 = Long.parseLong((s1));
num2 = num1 + 1;
// convert string to integer
// and add 1 and again convert
// back to string s2
s2 = Long.toString(num2);
int k = i + 1;
while (flag == 0) {
int l = s2.length();
// if s2 is not a substring
// of number than not possible
if (k + l > len) {
flag = 1;
break;
}
// if s2 is the next substring
// of the numeric string
if ((str.substring(k, k + l).equals(s2))) {
flag = 0;
// Increase num2 by 1 i.e the
// next number to be looked for
num2++;
k = k + l;
// check if string is fully
// traversed then break
if (k == len)
break;
s2 = Long.toString(num2);
l = s2.length();
if (k + 1 > len) {
// If next string doesnot occurs
// in a given numeric string
// then it is not possible
flag = 1;
break;
}
}
else
flag = 1;
}
// if the string was fully traversed
// and conditions were satisfied
if (flag == 0) {
System.out.println("Possible"
+ " " + s1);
break;
}
// if conditions failed to hold
else if (flag == 1 && i > len / 2 - 1) {
System.out.println("Not Possible");
break;
}
}
}
// Driver Code
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String str = "99100";
// Call the split function
// for splitting the string
split(str);
}
}
Python3
# Python3 program to split a numeric
# string in an Increasing
# sequence if possible
# Function accepts a string and
# checks if string can be split.
def split(Str) :
Len = len(Str)
# if there is only 1 number
# in the string then
# it is not possible to split it
if (Len == 1) :
print("Not Possible")
return
s1, s2 = "", ""
for i in range((Len // 2) + 1) :
flag = 0
# storing the substring from
# 0 to i+1 to form initial
# number of the increasing sequence
s1 = Str[0 : i + 1]
num1 = int(s1)
num2 = num1 + 1
# convert string to integer
# and add 1 and again convert
# back to string s2
s2 = str(num2)
k = i + 1
while (flag == 0) :
l = len(s2)
# if s2 is not a substring
# of number than not possible
if (k + l > Len) :
flag = 1
break
# if s2 is the next substring
# of the numeric string
if ((Str[k : k + l] == s2)) :
flag = 0
# Increase num2 by 1 i.e the
# next number to be looked for
num2 += 1
k = k + l
# check if string is fully
# traversed then break
if (k == Len) :
break
s2 = str(num2)
l = len(s2)
if (k + 1 > len) :
# If next string doesnot occurs
# in a given numeric string
# then it is not possible
flag = 1
break
else :
flag = 1
# if the string was fully traversed
# and conditions were satisfied
if (flag == 0) :
print("Possible", s1)
break
# if conditions failed to hold
elif (flag == 1 and i > (Len // 2) - 1) :
print("Not Possible")
break
# Driver code
Str = "99100"
# Call the split function
# for splitting the string
split(Str)
# This code is contributed by divyesh072019.
C#
// C# program to split a numeric
// string in an Increasing
// sequence if possible
using System;
class GFG
{
// Function accepts a
// string and checks if
// string can be split.
static void split(string str)
{
int len = str.Length;
// if there is only 1
// number in the string
// then it is not possible
// to split it
if (len == 1)
{
Console.WriteLine("Not Possible");
return;
}
string s1 = "", s2 = "";
long num1, num2;
for (int i = 0; i < len / 2; i++)
{
int flag = 0;
// storing the substring
// from 0 to i+1 to form
// initial number of the
// increasing sequence
s1 = str.Substring(0, i + 1);
num1 = Convert.ToInt64((s1));
num2 = num1 + 1;
// convert string to integer
// and add 1 and again convert
// back to string s2
s2 = num2.ToString();
int k = i + 1;
while (flag == 0)
{
int l = s2.Length;
// if s2 is not a substring
// of number than not possible
if (k + l > len)
{
flag = 1;
break;
}
// if s2 is the next
// substring of the
// numeric string
if ((str.Substring(k, l).Equals(s2)))
{
flag = 0;
// Increase num2 by 1 i.e
// the next number to be
// looked for
num2++;
k = k + l;
// check if string is fully
// traversed then break
if (k == len)
break;
s2 = num2.ToString();
l = s2.Length;
if (k + 1 > len)
{
// If next string doesnot
// occurs in a given numeric
// string then it is not
// possible
flag = 1;
break;
}
}
else
flag = 1;
}
// if the string was fully
// traversed and conditions
// were satisfied
if (flag == 0)
{
Console.WriteLine("Possible" +
" " + s1);
break;
}
// if conditions
// failed to hold
else if (flag == 1 &&
i > len / 2 - 1)
{
Console.WriteLine("Not Possible");
break;
}
}
}
// Driver Code
static void Main()
{
string str = "99100";
// Call the split function
// for splitting the string
split(str);
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Javascript
<script>
// JavaScript program to split a numeric
// string in an Increasing
// sequence if possible
// Function accepts a string and
// checks if string can be split.
function split(str)
{
let len = str.length;
// if there is only 1 number
// in the string then
// it is not possible to split it
if (len == 1) {
document.write("Not Possible","</br>");
return;
}
let s1 = "", s2 = "";
let num1, num2;
for (let i = 0; i <= Math.floor(len / 2); i++) {
let flag = 0;
// storing the substring from
// 0 to i+1 to form initial
// number of the increasing sequence
s1 = str.substring(0, i + 1);
num1 = parseInt(s1);
num2 = num1 + 1;
// convert string to integer
// and add 1 and again convert
// back to string s2
s2 = num2.toString(10);
let k = i + 1;
while (flag == 0) {
let l = s2.length;
// if s2 is not a substring
// of number than not possible
if (k + l > len) {
flag = 1;
break;
}
// if s2 is the next substring
// of the numeric string
if (str.substring(k, 2*k + l) == s2) {
flag = 0;
// Increase num2 by 1 i.e the
// next number to be looked for
num2++;
k = k + l;
// check if string is fully
// traversed then break
if (k == len)
break;
s2 = num2.toString(10);
l = s2.length;
if (k + 1 > len) {
// If next string doesnot occurs
// in a given numeric string
// then it is not possible
flag = 1;
break;
}
}
else flag = 1;
}
// if the string was fully traversed
// and conditions were satisfied
if (flag == 0) {
document.write("Possible " + s1,"</br>");
break;
}
// if conditions failed to hold
else if (flag == 1 && i > Math.floor(len / 2)- 1) {
document.write("Not Possible","</br>");
break;
}
}
}
// Driver code
let str = "99100";
// Call the split function
// for splitting the string
split(str);
// This code is contributed by shinjanpatra
</script>
Producción:
Possible 99
Complejidad de tiempo: O(n*n), donde n es la longitud de la string.
Espacio auxiliar: O(n), donde n es la longitud de la string.
Publicación traducida automáticamente
Artículo escrito por mohdanishh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA