Compruebe si una string numérica se puede dividir en substrings que tengan una diferencia entre números consecutivos igual a K

Dada una string numérica S que consta de N dígitos y un entero positivo K , la tarea es verificar si la string dada se puede dividir en más de una substring con una diferencia entre las substrings consecutivas igual a K .

Ejemplos:

Entrada: S = “8642”, K = 2
Salida: Sí
Explicación: Divida la string dada como {“8”, “6”, “4”, “2”}. Ahora, la diferencia entre las substrings consecutivas es K(= 2).

Entrada: S = “1009896”, K = 0
Salida: No

Enfoque: el problema dado se puede resolver generando todas las substrings posibles de la string dada y verificando si la concatenación de cualquier subconjunto de la substring generada es igual a la string dada S y la diferencia consecutiva del número como una substring es K , entonces imprimir Sí . De lo contrario , imprima No. Siga los pasos a continuación para resolver el problema:

• Iterar sobre el rango [1, N/2] usando la variable i y realizar los siguientes pasos:
  • Almacene la substring de longitud i y comenzando desde 0 en una variable X .
  • Genere la secuencia de tamaño N comenzando con este número X donde la diferencia de términos consecutivos es K . Guarde esta string en una prueba variable .
  • Si tanto la prueba de strings como S son iguales , actualice el valor de ans como verdadero y salga del bucle .
• Después de completar los pasos anteriores, si el valor de ans es falso , imprima «No» . De lo contrario, escriba «Sí» .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a numeric string
// can be split into substrings such that
// the difference between the consecutive
// substrings is K
void isPossible(string s, int K)
{
    bool valid = false;
    long firstx = -1;
 
    // Stores the size of the string
    int n = s.length();
 
    // Iterate over the range [1, N] and
    // try each possible starting number
    for (int i = 1; i <= n / 2; ++i) {
 
        long x = stol(s.substr(0, i));
        firstx = x;
 
        // Convert the number to string
        string test = to_string(x);
 
        // Build up a sequence
        // starting with the number
        while (test.length() < s.length()) {
            x -= K;
            test += to_string(x);
        }
 
        // Compare it with the
        // original string s
        if (test == s) {
            valid = true;
            break;
        }
    }
 
    // Print the result
    cout << ((valid == true) ? "Yes " : "No");
}
 
// Driver Code
int main()
{
    string S = "8642";
    int K = 2;
    isPossible(S, K);
 
    return 0;
}

# python 3 program for the above approach
 
# Function to check if a numeric string
# can be split into substrings such that
# the difference between the consecutive
# substrings is K
def isPossible(s,K):
    valid = False
    firstx = -1
 
    # Stores the size of the string
    n = len(s)
 
    # Iterate over the range [1, N] and
    # try each possible starting number
    for i in range(1,n//2+1,1):
        x = int(s[0:i])
        firstx = x
 
        # Convert the number to string
        test = str(x)
 
        # Build up a sequence
        # starting with the number
        while (len(test) < len(s)):
            x -= K
            test += str(x)
 
        # Compare it with the
        # original string s
        if (test == s):
            valid = True
            break
 
    # Print the result
    print("Yes") if valid == True else print("No")
 
# Driver Code
if __name__ == '__main__':
    S = "8642"
    K = 2
    isPossible(S, K)
     
    # This code is contributed by ipg2016107.

<script>
 
// JavaScript program for the above approach
 
// Function to check if a numeric string
// can be split into substrings such that
// the difference between the consecutive
// substrings is K
function isPossible(s, K)
{
    let valid = false;
    let firstx = -1;
 
    // Stores the size of the string
    let n = s.length;
 
    // Iterate over the range [1, N] and
    // try each possible starting number
    for (let i = 1; i <= n / 2; ++i) {
 
        let x = (s.substr(0, i));
        firstx = x;
 
        // Convert the number to string
        let test = x.toString();
 
        // Build up a sequence
        // starting with the number
        while (test.length < s.length) {
            x -= K;
            test += x.toString();
        }
 
        // Compare it with the
        // original string s
        if (test == s) {
            valid = true;
            break;
        }
    }
 
    // Print the result
    document.write((valid == true) ? "Yes " : "No");
}
// Driver Code
 
    let S = "8642";
    let K = 2;
    isPossible(S, K);
     
</script>

Yes

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)