Dado un número de 100 dígitos como máximo. Tenemos que comprobar si es posible, después de eliminar ciertos dígitos, obtener un número de al menos un dígito que sea divisible por 8. Está prohibido reordenar los dígitos.
Ejemplos:
Input : 1787075866 Output : Yes There exist more one or more subsequences divisible by 8. Example subsequences are 176, 16 and 8. Input : 6673177113 Output : No No subsequence is divisible by 8. Input : 3144 Output : Yes The subsequence 344 is divisible by 8.
Propiedad de la divisibilidad por ocho : un número se puede dividir por ocho si y solo si sus tres últimas cifras forman un número que se puede dividir por ocho. Por lo tanto, es suficiente probar solo los números que se pueden obtener del original al tachar y que contienen como máximo tres dígitos, es decir, verificamos todas las combinaciones de números de un dígito, dos dígitos y tres dígitos.
Método 1 (Fuerza bruta):
Aplicamos el enfoque de fuerza bruta. Permutamos todas las combinaciones posibles de un dígito, dos dígitos y tres dígitos usando una escalera iterativa. Si encontramos un número de un dígito divisible por 8 o una combinación de números de dos dígitos divisible por 8 o una combinación de números de tres dígitos divisible por 8, entonces esa será la solución a nuestro problema.
C++
// C++ program to check if a subsequence of digits
// is divisible by 8.
#include <bits/stdc++.h>
using namespace std;
// Function to calculate any permutation divisible
// by 8. If such permutation exists, the function
// will return that permutation else it will return -1
bool isSubSeqDivisible(string str)
{
// Converting string to integer array for ease
// of computations (Indexing in arr[] is
// considered to be starting from 1)
int l = str.length();
int arr[l];
for (int i = 0; i < l; i++)
arr[i] = str[i] - '0';
// Generating all possible permutations and checking
// if any such permutation is divisible by 8
for (int i = 0; i < l; i++) {
for (int j = i; j < l; j++) {
for (int k = j; k < l; k++) {
if (arr[i] % 8 == 0)
return true;
else if ((arr[i] * 10 + arr[j]) % 8 == 0 && i != j)
return true;
else if ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0 && i != j && j != k && i != k)
return true;
}
}
}
return false;
}
// Driver function
int main()
{
string str = "3144";
if (isSubSeqDivisible(str))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to check if a subsequence
// of digits is divisible by 8.
import java.io.*;
class GFG {
// Function to calculate any permutation
// divisible by 8. If such permutation
// exists, the function will return
// that permutation else it will return -1
static boolean isSubSeqDivisible(String str)
{
int i, j, k, l = str.length();
int arr[] = new int[l];
// Converting string to integer array for ease
// of computations (Indexing in arr[] is
// considered to be starting from 1)
for (i = 0; i < l; i++)
arr[i] = str.charAt(i) - '0';
// Generating all possible permutations
// and checking if any such
// permutation is divisible by 8
for (i = 0; i < l; i++) {
for (j = i; j < l; j++) {
for (k = j; k < l; k++) {
if (arr[i] % 8 == 0)
return true;
else if ((arr[i] * 10 + arr[j]) % 8 == 0 && i != j)
return true;
else if ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0
&& i != j && j != k && i != k)
return true;
}
}
}
return false;
}
// Driver function
public static void main(String args[])
{
String str = "3144";
if (isSubSeqDivisible(str))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Nikita Tiwari.
Python3
# Python3 program to
# check if a subsequence of digits
# is divisible by 8.
# Function to calculate any
# permutation divisible
# by 8. If such permutation
# exists, the function
# will return that permutation
# else it will return -1
def isSubSeqDivisible(st) :
l = len(st)
arr = [int(ch) for ch in st]
# Generating all possible
# permutations and checking
# if any such permutation
# is divisible by 8
for i in range(0, l) :
for j in range(i, l) :
for k in range(j, l) :
if (arr[i] % 8 == 0) :
return True
elif ((arr[i]*10 + arr[j])% 8 == 0 and i != j) :
return True
elif ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0 and i != j and j != k and i != k) :
return True
return False
# Driver function
st = "3144"
if (isSubSeqDivisible(st)) :
print("Yes")
else :
print("No")
# This code is contributed
# by Nikita Tiwari.
C#
// C# program to check if a subsequence
// of digits is divisible by 8.
using System;
class GFG {
// Function to calculate any permutation
// divisible by 8. If such permutation
// exists, the function will return
// that permutation else it will return -1
static bool isSubSeqDivisible(string str)
{
int i, j, k, l = str.Length;
int[] arr = new int[l];
// Converting string to integer array for ease
// of computations (Indexing in arr[] is
// considered to be starting from 1)
for (i = 0; i < n; i++)
arr[i] = str[i] - '0';
// Generating all possible permutations
// and checking if any such
// permutation is divisible by 8
for (i = 0; i < l; i++) {
for (j = i; j < l; j++) {
for (k = j; k < l; k++) {
if (arr[i] % 8 == 0)
return true;
else if ((arr[i] * 10 + arr[j])
% 8
== 0
&& i != j)
return true;
else if ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0
&& i != j && j != k
&& i != k)
return true;
}
}
}
return false;
}
// Driver function
public static void Main()
{
string str = "3144";
if (isSubSeqDivisible(str))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by vt_m.
Javascript
<script>
// JavaScript program to check if a subsequence
// of digits is divisible by 8.
// Function to calculate any permutation
// divisible by 8. If such permutation
// exists, the function will return
// that permutation else it will return -1
function isSubSeqDivisible(str)
{
let i, j, k, l = str.length;
let arr = [];
// Converting string to integer array for ease
// of computations (Indexing in arr[] is
// considered to be starting from 1)
for(i = 0; i < l; i++)
arr[i] = str[i] - '0';
// Generating all possible permutations
// and checking if any such
// permutation is divisible by 8
for(i = 0; i < l; i++)
{
for(j = i; j < l; j++)
{
for(k = j; k < l; k++)
{
if (arr[i] % 8 == 0)
return true;
else if ((arr[i] * 10 + arr[j]) %
8 == 0 && i != j)
return true;
else if ((arr[i] * 100 + arr[j] * 10 +
arr[k]) % 8 == 0 && i != j &&
j != k && i != k)
return true;
}
}
}
return false;
}
// Driver Code
let str = "3144";
if (isSubSeqDivisible(str))
document.write("Yes");
else
document.write("No");
// This code is contributed by susmitakundugoaldanga
</script>
PHP
<?php
// PHP program to check if a subsequence
// of digits is divisible by 8.
// Function to calculate any permutation
// divisible by 8. If such permutation
// exists, the function will return
// that permutation else it will return -1
function isSubSeqDivisible($str)
{
$l = strlen($str);
$arr = [];
// Converting string to integer array for ease
// of computations (Indexing in arr[] is
// considered to be starting from 1)
for($i = 0; $i < $l; $i++)
$arr[$i] = $str[$i] - '0';
// Generating all possible permutations
// and checking if any such
// permutation is divisible by 8
for($i = 0; $i < $l; $i++)
{
for($j = $i; $j < $l; $j++)
{
for($k = $j; $k < $l; $k++)
{
if ($arr[$i] % 8 == 0)
return true;
else if (($arr[$i] * 10 + $arr[$j]) %
8 == 0 && $i != $j)
return true;
else if (($arr[$i] * 100 + $arr[$j] * 10 +
$arr[$k]) % 8 == 0 && $i != $j &&
$j != $k && $i != $k)
return true;
}
}
}
return false;
}
// Driver Code
$str = "3144";
if (isSubSeqDivisible($str))
echo("Yes");
else
echo("No");
?>
// THIS CODE IS CONTRIBUTED BY GANGARAJULA LAXMI
Producción
Yes
Complejidad de tiempo: O(N 3 ), ya que estamos usando bucles anidados para atravesar N 3 veces. Donde N es la longitud de la string.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para la array. Donde N es la longitud de la string.
Método 2 (Programación dinámica):
aunque solo tenemos números de 100 dígitos, para ejemplos más largos, nuestro programa podría exceder el límite de tiempo dado.
Por lo tanto, optimizamos nuestro código utilizando un enfoque de programación dinámica .
Dejar
Sea el i-ésimo dígito de la muestra. Generamos una array dp[i][j], 1<=i<=n y 0<=j<8. El valor de dp es verdadero si podemos tachar algunos dígitos del prefijo de longitud i de modo que el número restante dé j módulo ocho, y falso en caso contrario. Para una comprensión amplia del concepto, si en un índice encontramos el elemento módulo 8 para ese índice ponemos el valor de
![dp[i][a_{i}mod8] = 1](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-0d0cbdebd5ded8b36f4ff7260c364d66_l3.png "Rendered by QuickLaTeX.com")
Para todos los demás números, nos basamos en un concepto simple de que la suma de ese dígito contribuirá con la información de un número divisible por 8, o se omitirá.
Nota: También hay que tener en cuenta que no podemos cambiar el orden
Ahora,
![dp[i][(j*10+a_{i}) mod 8]=max(dp[i][(j*10+a_{i}) mod 8], dp[i-1][j])](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-cbbf6ac3393be52efbcc312f2d0cc3f1_l3.png "Rendered by QuickLaTeX.com")
si sumamos el dígito actual al resultado anterior.
![dp[i][(j*10) mod 8]=max(dp[i][(j*10) mod 8], dp[i-1][j])](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-421ba2bb296723ea958d120cdd98a167_l3.png "Rendered by QuickLaTeX.com")
si excluimos el dígito actual en nuestra formación.
Ahora, si existiera tal número, obtendremos un «verdadero» para cualquier i en dp[i][0]
C++
// C++ program to find if there is a subsequence
// of digits divisible by 8.
#include <bits/stdc++.h>
using namespace std;
// Function takes in an array of numbers,
// dynamically goes on the location and
// makes combination of numbers.
bool isSubSeqDivisible(string str)
{
int n = str.length();
int dp[n + 1][10];
memset(dp, 0, sizeof(dp));
// Converting string to integer array for ease
// of computations (Indexing in arr[] is
// considered to be starting from 1)
int arr[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = str[i - 1] - '0';
for (int i = 1; i <= n; i++) {
dp[i][arr[i] % 8] = 1;
for (int j = 0; j < 8; j++) {
// If we consider the number in our combination,
// we add it to the previous combination
if (dp[i - 1][j] > dp[i][(j * 10 + arr[i]) % 8])
dp[i][(j * 10 + arr[i]) % 8] = dp[i - 1][j];
// If we exclude the number from our combination
if (dp[i - 1][j] > dp[i][j])
dp[i][j] = dp[i - 1][j];
}
}
for (int i = 1; i <= n; i++) {
// If at dp[i][0], we find value 1/true, it shows
// that the number exists at the value of 'i'
if (dp[i][0] == 1)
return true;
}
return false;
}
// Driver function
int main()
{
string str = "3144";
if (isSubSeqDivisible(str))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to find if there is a
// subsequence of digits divisible by 8.
import java.io.*;
import java.util.*;
class GFG {
// Function takes in an array of numbers,
// dynamically goes on the location and
// makes combination of numbers.
static boolean isSubSeqDivisible(String str)
{
int n = str.length();
int dp[][] = new int[n + 1][10];
// Converting string to integer array
// for ease of computations (Indexing in
// arr[] is considered to be starting
// from 1)
int arr[] = new int[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = (int)(str.charAt(i - 1) - '0');
for (int i = 1; i <= n; i++) {
dp[i][arr[i] % 8] = 1;
for (int j = 0; j < 8; j++) {
// If we consider the number in
// our combination, we add it to
// the previous combination
if (dp[i - 1][j] > dp[i][(j * 10
+ arr[i])
% 8])
dp[i][(j * 10 + arr[i]) % 8]
= dp[i - 1][j];
// If we exclude the number from
// our combination
if (dp[i - 1][j] > dp[i][j])
dp[i][j] = dp[i - 1][j];
}
}
for (int i = 1; i <= n; i++) {
// If at dp[i][0], we find value 1/true,
// it shows that the number exists at
// the value of 'i'
if (dp[i][0] == 1)
return true;
}
return false;
}
// Driver function
public static void main(String args[])
{
String str = "3144";
if (isSubSeqDivisible(str))
System.out.println("Yes");
else
System.out.println("No");
}
}
/* This code is contributed by Nikita Tiwari.*/
Python3
# Python3 program to find
# if there is a subsequence
# of digits divisible by 8.
# Function takes in an array of numbers,
# dynamically goes on the location and
# makes combination of numbers.
def isSubSeqDivisible(str):
n = len(str)
dp = [[0 for i in range(10)]
for i in range(n + 1)]
# Converting string to integer
# array for ease of computations
# (Indexing in arr[] is considered
# to be starting from 1)
arr = [0 for i in range(n + 1)]
for i in range(1, n + 1):
arr[i] = int(str[i - 1]);
for i in range(1, n + 1):
dp[i][arr[i] % 8] = 1;
for j in range(8):
# If we consider the number
# in our combination, we add
# it to the previous combination
if (dp[i - 1][j] > dp[i][(j * 10 + arr[i]) % 8]):
dp[i][(j * 10 + arr[i]) % 8] = dp[i - 1][j]
# If we exclude the number
# from our combination
if (dp[i - 1][j] > dp[i][j]):
dp[i][j] = dp[i - 1][j]
for i in range(1, n + 1):
# If at dp[i][0], we find
# value 1/true, it shows
# that the number exists
# at the value of 'i'
if (dp[i][0] == 1):
return True
return False
# Driver Code
str = "3144"
if (isSubSeqDivisible(str)):
print("Yes")
else:
print("No")
# This code is contributed
# by sahilshelangia
C#
// C# program to find if there is a
// subsequence of digits divisible by 8.
using System;
class GFG {
// Function takes in an array of numbers,
// dynamically goes on the location and
// makes combination of numbers.
static bool isSubSeqDivisible(String str)
{
int n = str.Length;
int[, ] dp = new int[n + 1, 10];
// Converting string to integer array
// for ease of computations (Indexing in
// arr[] is considered to be starting
// from 1)
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = (int)(str[i - 1] - '0');
for (int i = 1; i <= n; i++) {
dp[i, arr[i] % 8] = 1;
for (int j = 0; j < 8; j++) {
// If we consider the number in
// our combination, we add it to
// the previous combination
if (dp[i - 1, j] > dp[i, (j * 10
+ arr[i])
% 8])
dp[i, (j * 10 + arr[i]) % 8]
= dp[i - 1, j];
// If we exclude the number from
// our combination
if (dp[i - 1, j] > dp[i, j])
dp[i, j] = dp[i - 1, j];
}
}
for (int i = 1; i <= n; i++) {
// If at dp[i][0], we find value
// 1/true, it shows that the number
// exists at the value of 'i'
if (dp[i, 0] == 1)
return true;
}
return false;
}
// Driver function
public static void Main()
{
string str = "3144";
if (isSubSeqDivisible(str))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find if there
// is a subsequence of digits
// divisible by 8.
// Function takes in an array of numbers,
// dynamically goes on the location and
// makes combination of numbers.
function isSubSeqDivisible($str)
{
$n = strlen($str);
$dp = array_fill(0, $n + 1,
array_fill(0, 10, NULL));
// Converting string to integer
// array for ease of computations
// (Indexing in arr[] is considered
// to be starting from 1)
$arr = array_fill(0, ($n + 1), NULL);
for ($i = 1; $i <= $n; $i++)
$arr[$i] = $str[$i - 1] - '0';
for ($i = 1; $i <= $n; $i++)
{
$dp[$i][$arr[$i] % 8] = 1;
for ($j = 0; $j < 8; $j++)
{
// If we consider the number in
// our combination, we add it to
// the previous combination
if ($dp[$i - 1][$j] > $dp[$i][($j * 10 +
$arr[$i]) % 8])
$dp[$i][($j * 10 +
$arr[$i]) % 8] = $dp[$i - 1][$j];
// If we exclude the number
// from our combination
if ($dp[$i - 1][$j] > $dp[$i][$j])
$dp[$i][$j] = $dp[$i - 1][$j];
}
}
for ($i = 1; $i <= $n; $i++)
{
// If at dp[i][0], we find value 1/true,
// it shows that the number exists at
// the value of 'i'
if ($dp[$i][0] == 1)
return true;
}
return false;
}
// Driver Code
$str = "3144";
if (isSubSeqDivisible($str))
echo "Yes";
else
echo "No";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find if there is a
// subsequence of digits divisible by 8.
// Function takes in an array of numbers,
// dynamically goes on the location and
// makes combination of numbers.
function isSubSeqDivisible(str)
{
let n = str.length;
let dp = new Array(n + 1);
for(let i = 0; i < 10; i++)
{
dp[i] = new Array(10);
for(let j = 0; j < 10; j++)
{
dp[i][j] = 0;
}
}
// Converting string to integer array
// for ease of computations (Indexing in
// arr[] is considered to be starting
// from 1)
let arr = new Array(n + 1);
for (let i = 1; i <= n; i++)
arr[i] = (str[i - 1].charCodeAt() - '0'.charCodeAt());
for (let i = 1; i <= n; i++) {
dp[i][arr[i] % 8] = 1;
for (let j = 0; j < 8; j++) {
// If we consider the number in
// our combination, we add it to
// the previous combination
if (dp[i - 1][j] > dp[i][(j * 10 + arr[i]) % 8])
dp[i][(j * 10 + arr[i]) % 8] = dp[i - 1][j];
// If we exclude the number from
// our combination
if (dp[i - 1][j] > dp[i][j])
dp[i][j] = dp[i - 1][j];
}
}
for (let i = 1; i <= n; i++) {
// If at dp[i][0], we find value 1/true,
// it shows that the number exists at
// the value of 'i'
if (dp[i][0] == 1)
return true;
}
return false;
}
let str = "3144";
if (isSubSeqDivisible(str))
document.write("Yes");
else
document.write("No");
</script>
Producción
Yes
Complejidad de tiempo: O(n), al usar el enfoque dinámico, nuestra complejidad de tiempo se reduce a O(8*n) ya que estamos usando recorrido lineal. Donde 8 es a partir del cual el número debe ser divisible y n es la longitud de nuestra entrada.
Espacio auxiliar: O(n), ya que estamos usando espacio extra para la array dp. Donde N es la longitud de nuestra entrada.
Método 3
Para este problema, simplemente necesitamos verificar si existe una subsecuencia de dos dígitos divisible por 8 (prueba de divisibilidad para 8)
Primero encontramos todos los números de 2 dígitos divisibles por 8 y mapeamos el dígito del lugar de las decenas con el dígito del lugar de la unidad,
es decir :- 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96
Ignore 48 ya que 8 siempre es divisible por 8 de manera similar 80 y 88 tienen 8 en ellos que hacen que tal subsecuencia siempre sea divisible por 8
Así que mapa 1 a 6, 2 a 4, 3 a 2, y así sucesivamente usando mapa, es decir, mapa stl en C++.
Después de construir el mapa, atravesamos la string desde el último índice y verificamos si el valor asignado del número de índice actual se visita o no, por lo tanto, necesitamos una array visitada para esto que almacenará verdadero si se visita el número, de lo contrario, falso,
por ejemplo: – 3769
El primer carácter del último índice es 9, por lo que verificamos si se visita 6 (es decir, 96 es una subsecuencia o no), marcamos 9 en la array visitada,
el siguiente carácter es 6, por lo que verificamos si se visitó 4 (es decir, 64), marcamos 6 en el el siguiente carácter de la array visitada
es 7, por lo que verificamos que se haya visitado 2 (es decir, 72), marcamos 7 en la array visitada, el
siguiente carácter es 3, por lo que verificamos que se haya visitado 6 (es decir, 36), sí, 6 está marcado, por lo tanto, imprimimos Sí.
C++
// C++ program to check if given string
// has a subsequence divisible by 8
#include<bits/stdc++.h>
using namespace std;
// Driver function
int main(){
string str = "129365";
// map key will be tens place digit of number
// that is divisible by 8 and value will
// be units place digit
map<int, int> mp;
// For filling the map let start
// with initial value 8
int no = 8;
while(no < 100){
no = no + 8;
// key is digit at tens place and value is
// digit at units place mp.insert({key, value})
mp.insert({(no / 10) % 10, no % 10});
}
// Create a hash to check if we visited a number
vector<bool> visited(10, false);
int i;
// Iterate from last index to 0th index
for(i = str.length() - 1; i >= 0; i--){
// If 8 is present in string then
// 8 divided 8 hence print yes
if(str[i] == '8')
{
cout << "Yes";
break;
}
// considering present character as the second
// digit of two digits no we check if the value
// of this key is marked in hash or not
// If marked then we a have a number divisible by 8
if(visited[mp[str[i] - '0']]){
cout << "Yes";
break;
}
visited[str[i] - '0'] = true;
}
// If no subsequence divisible by 8
if(i == -1)
cout << "No";
return 0;
}
Java
// Java program to check if
// given String has a subsequence
// divisible by 8
import java.util.*;
class GFG{
// Driver code
public static void main(String[] args)
{
String str = "129365";
// map key will be tens place
// digit of number that is
// divisible by 8 and value will
// be units place digit
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// For filling the map let start
// with initial value 8
int no = 8;
while(no < 100)
{
no = no + 8;
// key is digit at tens place
// and value is digit at units
// place mp.add({key, value})
//if(mp.containsKey((no / 10) % 10))
mp.put((no / 10) % 10, no % 10);
}
// Create a hash to check if
// we visited a number
boolean[] visited = new boolean[10];
int i;
// Iterate from last index
// to 0th index
for(i = str.length() - 1;
i >= 0; i--)
{
// If 8 is present in String then
// 8 divided 8 hence print yes
if(str.charAt(i) == '8')
{
System.out.print("Yes");
break;
}
// considering present character
// as the second digit of two
// digits no we check if the value
// of this key is marked in hash or not
// If marked then we a have a number
// divisible by 8
if(visited[mp.get(str.charAt(i)- '0')])
{
System.out.print("Yes");
break;
}
visited[str.charAt(i) - '0'] = true;
}
// If no subsequence divisible
// by 8
if(i == -1)
System.out.print("No");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to check if given string
# has a subsequence divisible by 8
Str = "129365"
# map key will be tens place digit of number
# that is divisible by 8 and value will
# be units place digit
mp = {}
# For filling the map let start
# with initial value 8
no = 8
while(no < 100) :
no = no + 8
# key is digit at tens place and value is
# digit at units place mp.insert({key, value})
mp[(no // 10) % 10] = no % 10
# Create a hash to check if we visited a number
visited = [False] * 10
# Iterate from last index to 0th index
for i in range(len(Str) - 1, -1, -1) :
# If 8 is present in string then
# 8 divided 8 hence print yes
if(Str[i] == '8') :
print("Yes", end = "")
break
# considering present character as the second
# digit of two digits no we check if the value
# of this key is marked in hash or not
# If marked then we a have a number divisible by 8
if visited[mp[ord(Str[i]) - ord('0')]] :
print("Yes", end = "")
break
visited[ord(Str[i]) - ord('0')] = True
# If no subsequence divisible by 8
if(i == -1) :
print("No")
# This code is contributed by divyeshrabadiya07
C#
// C# program to check if given
// String has a subsequence
// divisible by 8
using System;
using System.Collections.Generic;
class GFG{
// Driver code
public static void Main(String[] args)
{
String str = "129365";
// Map key will be tens place
// digit of number that is
// divisible by 8 and value will
// be units place digit
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// For filling the map let start
// with initial value 8
int no = 8;
while (no < 100)
{
no = no + 8;
// Key is digit at tens place
// and value is digit at units
// place mp.Add({key, value})
if (mp.ContainsKey((no / 10) % 10))
mp[(no / 10) % 10] = no % 10;
else
mp.Add((no / 10) % 10, no % 10);
}
// Create a hash to check if
// we visited a number
bool[] visited = new bool[10];
int i;
// Iterate from last index
// to 0th index
for(i = str.Length - 1; i >= 0; i--)
{
// If 8 is present in String then
// 8 divided 8 hence print yes
if (str[i] == '8')
{
Console.Write("Yes");
break;
}
// Considering present character
// as the second digit of two
// digits no we check if the value
// of this key is marked in hash or not
// If marked then we a have a number
// divisible by 8
if (visited[mp[str[i] - '0']])
{
Console.Write("Yes");
break;
}
visited[str[i] - '0'] = true;
}
// If no subsequence divisible
// by 8
if (i == -1)
Console.Write("No");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to check if
// given String has a subsequence
// divisible by 8
// Driver code
let str = "129365";
// map key will be tens place
// digit of number that is
// divisible by 8 and value will
// be units place digit
let mp = new Map();
// For filling the map let start
// with initial value 8
let no = 8;
while(no < 100)
{
no = no + 8;
// key is digit at tens place
// and value is digit at units
// place mp.add({key, value})
//if(mp.containsKey((no / 10) % 10))
mp.set((Math.floor(no / 10)) % 10, no % 10);
}
// Create a hash to check if
// we visited a number
let visited = new Array(10);
for(let i=0;i<visited.length;i++)
{
visited[i]=false;
}
let i;
// Iterate from last index
// to 0th index
for(i = str.length - 1;
i >= 0; i--)
{
// If 8 is present in String then
// 8 divided 8 hence print yes
if(str[i] == '8')
{
document.write("Yes");
break;
}
// considering present character
// as the second digit of two
// digits no we check if the value
// of this key is marked in hash or not
// If marked then we a have a number
// divisible by 8
if(visited[mp.get(str[i].charCodeAt(0)-
'0'.charCodeAt(0))])
{
document.write("Yes");
break;
}
visited[str[i].charCodeAt(0) -
'0'.charCodeAt(0)] = true;
}
// If no subsequence divisible
// by 8
if(i == -1)
document.write("No");
// This code is contributed by rag2127
</script>
Producción
Yes
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es la longitud de nuestra entrada.
Espacio auxiliar: O(1), como si mirara de cerca, la array visitada siempre tendrá 10 campos y el mapa siempre tendrá el mismo tamaño, por lo que la complejidad del espacio será O(1).