Dividir una string numérica

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *