Dado un gran número N y la tarea es verificar si alguna permutación de un gran número es divisible por 8.
Ejemplos:
Input: N = 31462708 Output: Yes Many of permutation of number N like 34678120, 34278160 are divisible by 8. Input: 75 Output: No
Un enfoque ingenuo es generar todas las permutaciones del número N y verificar si (N % 8 == 0) y devolver verdadero si alguna de las permutaciones es divisible por 8.
Un enfoque eficiente es usar el hecho de que si los últimos tres dígitos de un número son divisibles por 8, entonces el número también es divisible por 8. A continuación se muestran los pasos necesarios:
- Use una tabla hash para contar las ocurrencias de todos los dígitos en el número dado.
- Poligonal para todos los números de tres dígitos que son divisibles por 8.
- Compruebe si los dígitos del número de tres dígitos están en la tabla hash.
- En caso afirmativo, se puede formar un número por permutación donde los últimos tres dígitos se combinan para formar el número de tres dígitos.
- Si no se puede formar ninguno de los números de tres dígitos, devuelve falso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if any permutation of
// a large number is divisible by 8 or not
#include <bits/stdc++.h>
using namespace std;
// Function to check if any permutation
// of a large number is divisible by 8
bool solve(string n, int l)
{
// Less than three digit number
// can be checked directly.
if (l < 3) {
if (stoi(n) % 8 == 0)
return true;
// check for the reverse of a number
reverse(n.begin(), n.end());
if (stoi(n) % 8 == 0)
return true;
return false;
}
// Stores the Frequency of characters in the n.
int hash[10] = { 0 };
for (int i = 0; i < l; i++)
hash[n[i] - '0']++;
// Iterates for all three digit numbers
// divisible by 8
for (int i = 104; i < 1000; i += 8) {
int dup = i;
// stores the frequency of all single
// digit in three-digit number
int freq[10] = { 0 };
freq[dup % 10]++;
dup = dup / 10;
freq[dup % 10]++;
dup = dup / 10;
freq[dup % 10]++;
dup = i;
// check if the original number has
// the digit
if (freq[dup % 10] > hash[dup % 10])
continue;
dup = dup / 10;
if (freq[dup % 10] > hash[dup % 10])
continue;
dup = dup / 10;
if (freq[dup % 10] > hash[dup % 10])
continue;
return true;
}
// when all are checked its not possible
return false;
}
// Driver Code
int main()
{
string number = "31462708";
int l = number.length();
if (solve(number, l))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to check if
// any permutation of a large
// number is divisible by 8 or not
import java.util.*;
class GFG
{
// Function to check if any
// permutation of a large
// number is divisible by 8
public static boolean solve(String n, int l)
{
// Less than three digit number
// can be checked directly.
if (l < 3)
{
if (Integer.parseInt(n) % 8 == 0)
return true;
// check for the reverse
// of a number
n = new String((new StringBuilder()).append(n).reverse());
if (Integer.parseInt(n) % 8 == 0)
return true;
return false;
}
// Stores the Frequency of
// characters in the n.
int []hash = new int[10];
for (int i = 0; i < l; i++)
hash[n.charAt(i) - '0']++;
// Iterates for all
// three digit numbers
// divisible by 8
for (int i = 104; i < 1000; i += 8)
{
int dup = i;
// stores the frequency of
// all single digit in
// three-digit number
int []freq = new int[10];
freq[dup % 10]++;
dup = dup / 10;
freq[dup % 10]++;
dup = dup / 10;
freq[dup % 10]++;
dup = i;
// check if the original
// number has the digit
if (freq[dup % 10] >
hash[dup % 10])
continue;
dup = dup / 10;
if (freq[dup % 10] >
hash[dup % 10])
continue;
dup = dup / 10;
if (freq[dup % 10] >
hash[dup % 10])
continue;
return true;
}
// when all are checked
// its not possible
return false;
}
// Driver Code
public static void main(String[] args)
{
String number = "31462708";
int l = number.length();
if (solve(number, l))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed
// by Harshit Saini
Python3
# Python3 program to check if
# any permutation of a large
# number is divisible by 8 or not
# Function to check if any
# permutation of a large
# number is divisible by 8
def solve(n, l):
# Less than three digit
# number can be checked
# directly.
if l < 3:
if int(n) % 8 == 0:
return True
# check for the reverse
# of a number
n = n[::-1]
if int(n) % 8 == 0:
return True
return False
# Stores the Frequency of
# characters in the n.
hash = 10 * [0]
for i in range(0, l):
hash[int(n[i]) - 0] += 1;
# Iterates for all
# three digit numbers
# divisible by 8
for i in range(104, 1000, 8):
dup = i
# stores the frequency
# of all single digit
# in three-digit number
freq = 10 * [0]
freq[int(dup % 10)] += 1;
dup = dup / 10
freq[int(dup % 10)] += 1;
dup = dup / 10
freq[int(dup % 10)] += 1;
dup = i
# check if the original
# number has the digit
if (freq[int(dup % 10)] >
hash[int(dup % 10)]):
continue;
dup = dup / 10;
if (freq[int(dup % 10)] >
hash[int(dup % 10)]):
continue;
dup = dup / 10
if (freq[int(dup % 10)] >
hash[int(dup % 10)]):
continue;
return True
# when all are checked
# its not possible
return False
# Driver Code
if __name__ == "__main__":
number = "31462708"
l = len(number)
if solve(number, l):
print("Yes")
else:
print("No")
# This code is contributed
# by Harshit Saini
C#
// C# program to check if
// any permutation of a large
// number is divisible by 8 or not
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if any
// permutation of a large
// number is divisible by 8
public static bool solve(String n, int l)
{
// Less than three digit number
// can be checked directly.
if (l < 3)
{
if (int.Parse(n) % 8 == 0)
return true;
// check for the reverse
// of a number
n = reverse(n);
if (int.Parse(n) % 8 == 0)
return true;
return false;
}
// Stores the Frequency of
// characters in the n.
int []hash = new int[10];
for (int i = 0; i < l; i++)
hash[n[i] - '0']++;
// Iterates for all
// three digit numbers
// divisible by 8
for (int i = 104; i < 1000; i += 8)
{
int dup = i;
// stores the frequency of
// all single digit in
// three-digit number
int []freq = new int[10];
freq[dup % 10]++;
dup = dup / 10;
freq[dup % 10]++;
dup = dup / 10;
freq[dup % 10]++;
dup = i;
// check if the original
// number has the digit
if (freq[dup % 10] >
hash[dup % 10])
continue;
dup = dup / 10;
if (freq[dup % 10] >
hash[dup % 10])
continue;
dup = dup / 10;
if (freq[dup % 10] >
hash[dup % 10])
continue;
return true;
}
// when all are checked
// its not possible
return false;
}
static String reverse(String input)
{
char[] a = input.ToCharArray();
int l, r = 0;
r = a.Length - 1;
for (l = 0; l < r; l++, r--)
{
// Swap values of l and r
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.Join("",a);
}
// Driver Code
public static void Main(String[] args)
{
String number = "31462708";
int l = number.Length;
if (solve(number, l))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Princi Singh
PHP
<?php
error_reporting(0);
// PHP program to check
// if any permutation of
// a large number is
// divisible by 8 or not
// Function to check if
// any permutation of a
// large number is divisible by 8
function solve($n, $l)
{
// Less than three digit
// number can be checked
// directly.
if ($l < 3)
{
if (intval($n) % 8 == 0)
return true;
// check for the
// reverse of a number
strrev($n);
if (intval($n) % 8 == 0)
return true;
return false;
}
// Stores the Frequency of
// characters in the n.
$hash[10] = array(0);
for ($i = 0; $i < $l; $i++)
$hash[$n[$i] - '0']++;
// Iterates for all three
// digit numbers divisible by 8
for ($i = 104;
$i < 1000; $i += 8)
{
$dup = $i;
// stores the frequency of
// all single digit in
// three-digit number
$freq[10] = array(0);
$freq[$dup % 10]++;
$dup = $dup / 10;
$freq[$dup % 10]++;
$dup = $dup / 10;
$freq[$dup % 10]++;
$dup = $i;
// check if the original
// number has the digit
if ($freq[$dup % 10] >
$hash[$dup % 10])
continue;
$dup = $dup / 10;
if ($freq[$dup % 10] >
$hash[$dup % 10])
continue;
$dup = $dup / 10;
if ($freq[$dup % 10] >
$hash[$dup % 10])
continue;
return true;
}
// when all are checked
// its not possible
return false;
}
// Driver Code
$number = "31462708";
$l = strlen($number);
if (solve($number, $l))
echo "Yes";
else
echo "No";
// This code is contributed
// by Akanksha Rai(Abby_akku)
Javascript
<script>
// JavaScript program to check if
// any permutation of a large
// number is divisible by 8 or not
// Function to check if any
// permutation of a large
// number is divisible by 8
function solve(n, l) {
// Less than three digit number
// can be checked directly.
if (l < 3) {
if (parseInt(n) % 8 === 0) return true;
// check for the reverse
// of a number
n = reverse(n);
if (parseInt(n) % 8 === 0) return true;
return false;
}
// Stores the Frequency of
// characters in the n.
var hash = new Array(10).fill(0);
for (var i = 0; i < l; i++) hash[parseInt(n[i]) - 0]++;
// Iterates for all
// three digit numbers
// divisible by 8
for (var i = 104; i < 1000; i += 8) {
var dup = i;
// stores the frequency of
// all single digit in
// three-digit number
var freq = new Array(10).fill(0);
freq[parseInt(dup % 10)]++;
dup = dup / 10;
freq[parseInt(dup % 10)]++;
dup = dup / 10;
freq[parseInt(dup % 10)]++;
dup = i;
// check if the original
// number has the digit
if (freq[parseInt(dup % 10)] > hash[parseInt(dup % 10)])
continue;
dup = dup / 10;
if (freq[parseInt(dup % 10)] > hash[parseInt(dup % 10)])
continue;
dup = dup / 10;
if (freq[parseInt(dup % 10)] > hash[parseInt(dup % 10)])
continue;
return true;
}
// when all are checked
// its not possible
return false;
}
function reverse(input) {
var a = input.split("");
var l,
r = 0;
r = a.length - 1;
for (l = 0; l < r; l++, r--) {
// Swap values of l and r
var temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return a.join("");
}
// Driver Code
var number = "31462708";
var l = number.length;
if (solve(number, l))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad temporal: O(L), donde L es el número de dígitos del número.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA