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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción:
121400
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(1)