Subsecuencia más larga de una string numérica divisible por K

Dado un entero K y una string numérica str , la tarea es encontrar la subsecuencia más larga de la string dada que sea divisible por K .

Ejemplos:

Entrada: str = “121400”, K = 8
Salida: 121400
Explicación:
Dado que toda la string es divisible por 8, la string completa es la respuesta.

Entrada: str: “7675437”, K = 64
Salida: 64
Explicación:
La subsecuencia más larga de la string que es divisible por 64, es “64” en sí.

Enfoque: la idea es encontrar todas las subsecuencias de la string dada y, para cada subsecuencia, verificar si su representación entera es divisible por K o no. Siga los pasos a continuación para resolver el problema:

• Atraviesa la cuerda . Por cada personaje encontrado, existen dos posibilidades.
• Considere el carácter actual en la subsecuencia o no. Para ambos casos, continúe con los siguientes caracteres de la string y encuentre la subsecuencia más larga que sea divisible por K .
• Compare las subsecuencias más largas obtenidas anteriormente con la longitud máxima actual de la subsecuencia más larga y actualice en consecuencia.
• Repita los pasos anteriores para cada carácter de la string y, finalmente, imprima la longitud máxima obtenida.

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 if the integer representation
// of the current string is divisible by K
bool isdivisible(string& newstr, long long K)
{
    // Stores the integer
    // representation of the string
    long long num = 0;
 
    for (int i = 0; i < newstr.size(); i++) {
        num = num * 10 + newstr[i] - '0';
    }
 
    // Check if the num is
    // divisible by K
    if (num % K == 0)
        return true;
 
    else
        return false;
}
 
// Function to find the longest subsequence
// which is divisible by K
void findLargestNo(string& str, string& newstr,
                string& ans, int index,
                long long K)
{
 
    if (index == (int)str.length()) {
 
        // If the number is divisible by K
        if (isdivisible(newstr, K)) {
 
            // If current number is the
            // maximum obtained so far
            if ((ans < newstr
                && ans.length() == newstr.length())
                || newstr.length() > ans.length()) {
                ans = newstr;
            }
        }
 
        return;
    }
 
    string x = newstr + str[index];
 
    // Include the digit at current index
    findLargestNo(str, x, ans, index + 1, K);
 
    // Exclude the digit at current index
    findLargestNo(str, newstr, ans, index + 1, K);
}
 
// Driver Code
int main()
{
 
    string str = "121400";
 
    string ans = "", newstr = "";
 
    long long K = 8;
 
    findLargestNo(str, newstr, ans, 0, K);
 
    // Printing the largest number
    // which is divisible by K
    if (ans != "")
        cout << ans << endl;
 
    // If no number is found
    // to be divisible by K
    else
        cout << -1 << endl;
}

// Java program for the
// above approach
import java.util.*;
import java.lang.*;
 
class GFG{
     
// Function to if the integer representation
// of the current string is divisible by K
static boolean isdivisible(StringBuilder newstr,
                           long K)
{
     
    // Stores the integer
    // representation of the string
    long num = 0;
   
    for(int i = 0; i < newstr.length(); i++)
    {
        num = num * 10 + newstr.charAt(i) - '0';
    }
   
    // Check if the num is
    // divisible by K
    if (num % K == 0)
        return true;
    else
        return false;
}
   
// Function to find the longest
// subsequence which is divisible
// by K
static void findLargestNo(String str, StringBuilder newstr,
                          StringBuilder ans, int index,
                          long K)
{
    if (index == str.length())
    {
         
        // If the number is divisible by K
        if (isdivisible(newstr, K))
        {
             
            // If current number is the
            // maximum obtained so far
            if ((newstr.toString().compareTo(ans.toString()) > 0 &&
                ans.length() == newstr.length()) ||
                newstr.length() > ans.length())
            {
                ans.setLength(0);
                ans.append(newstr);
            }
        }
        return;
    }
   
    StringBuilder x = new StringBuilder(
        newstr.toString() + str.charAt(index));
   
    // Include the digit at current index
    findLargestNo(str, x, ans, index + 1, K);
   
    // Exclude the digit at current index
    findLargestNo(str, newstr, ans, index + 1, K);
} 
 
// Driver code
public static void main (String[] args)
{
    String str = "121400";
     
    StringBuilder ans = new StringBuilder(),
               newstr = new StringBuilder();
     
     long K = 8;
     
    findLargestNo(str, newstr, ans, 0, K);
     
    // Printing the largest number
    // which is divisible by K
    if (ans.toString() != "")
        System.out.println(ans);
     
    // If no number is found
    // to be divisible by K
    else
        System.out.println(-1);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function to if the integer representation
# of the current string is divisible by K
def isdivisible(newstr, K):
     
    # Stores the integer
    # representation of the string
    num = 0;
 
    for i in range(len(newstr)):
        num = num * 10 + int(newstr[i])
 
    # Check if the num is
    # divisible by K
    if (num % K == 0):
        return True
    else:
        return False
         
# Function to find the longest subsequence
# which is divisible by K
def findLargestNo(str, newstr, ans, index, K):
     
    if (index == len(str)):
         
        # If the number is divisible by K
        if (isdivisible(newstr, K)):
             
            # If current number is the
            # maximum obtained so far
            if ((ans < newstr and len(ans) == len(newstr)) or len(newstr) > len(ans)):
                ans = newstr
         
        return ans
 
    x = newstr + str[index];
 
    # Include the digit at current index
    ans = findLargestNo(str, x, ans, index + 1, K);
 
    # Exclude the digit at current index
    ans = findLargestNo(str, newstr, ans, index + 1, K);
 
    return ans;
 
# Driver Code
str = "121400";
ans = ""
newstr = "";
K = 8;
ans = findLargestNo(str, newstr, ans, 0, K);
 
# Printing the largest number
# which is divisible by K
if (ans != "") :
    print(ans)
     
# If no number is found
# to be divisible by K
else:
    print( -1)
 
# This code is contributed by phasing17

// C# program for the above approach
using System;
using System.Text;
 
class GFG{
     
// Function to if the integer representation
// of the current string is divisible by K
static bool isdivisible(StringBuilder newstr,
                        long K)
{
     
    // Stores the integer representation
    // of the string
    long num = 0;
   
    for(int i = 0; i < newstr.Length; i++)
    {
        num = num * 10 + newstr[i] - '0';
    }
     
    // Check if the num is
    // divisible by K
    if (num % K == 0)
        return true;
    else
        return false;
}
   
// Function to find the longest
// subsequence which is divisible
// by K
static void findLargestNo(String str, StringBuilder newstr,
                          StringBuilder ans, int index,
                          long K)
{
    if (index == str.Length)
    {
         
        // If the number is divisible by K
        if (isdivisible(newstr, K))
        {
             
            // If current number is the
            // maximum obtained so far
            if ((newstr.ToString().CompareTo(ans.ToString()) > 0 &&
                ans.Length == newstr.Length) ||
                newstr.Length > ans.Length)
            {
                ans.EnsureCapacity(0);//.SetLength(0);
                ans.Append(newstr);
            }
        }
        return;
    }
   
    StringBuilder x = new StringBuilder(
        newstr.ToString() + str[index]);
         
    // Include the digit at current index
    findLargestNo(str, x, ans, index + 1, K);
   
    // Exclude the digit at current index
    findLargestNo(str, newstr, ans, index + 1, K);
} 
 
// Driver code
public static void Main(String[] args)
{
    String str = "121400";
     
    StringBuilder ans = new StringBuilder(),
               newstr = new StringBuilder();
     
     long K = 8;
     
    findLargestNo(str, newstr, ans, 0, K);
     
    // Printing the largest number
    // which is divisible by K
    if (ans.ToString() != "")
        Console.WriteLine(ans);
     
    // If no number is found
    // to be divisible by K
    else
        Console.WriteLine(-1);
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program for the above approach
 
// Function to if the integer representation
// of the current string is divisible by K
function isdivisible(newstr, K)
{
     
    // Stores the integer
    // representation of the string
    var num = 0;
 
    for(var i = 0; i < newstr.length; i++)
    {
        num = num * 10 + newstr[i].charCodeAt(0) -
                               '0'.charCodeAt(0);
    }
 
    // Check if the num is
    // divisible by K
    if (num % K == 0)
        return true;
    else
        return false;
}
 
// Function to find the longest subsequence
// which is divisible by K
function findLargestNo(str, newstr, ans, index, K)
{
    if (index == str.length)
    {
         
        // If the number is divisible by K
        if (isdivisible(newstr, K))
        {
             
            // If current number is the
            // maximum obtained so far
            if ((ans < newstr &&
                 ans.length == newstr.length) ||
                 newstr.length > ans.length)
            {
                ans = newstr;
            }
        }
        return ans;
    }
 
    var x = newstr + str[index];
 
    // Include the digit at current index
    ans = findLargestNo(str, x, ans,
                        index + 1, K);
 
    // Exclude the digit at current index
    ans = findLargestNo(str, newstr, ans,
                        index + 1, K);
 
    return ans;
}
 
// Driver Code
var str = "121400";
var ans = "", newstr = "";
var K = 8;
ans = findLargestNo(str, newstr, ans, 0, K);
 
// Printing the largest number
// which is divisible by K
if (ans != "")
    document.write(ans)
     
// If no number is found
// to be divisible by K
else
    document.write( -1)
 
// This code is contributed by itsok
 
</script>

121400

Complejidad de Tiempo: O(N * 2 ^N )
Espacio Auxiliar: O(1)