Dado un número entero N . La tarea es verificar si alguna de sus permutaciones es un palíndromo y divisible por 3 o no.
Ejemplos :
Input : N = 34734 Output : True
Input : N = 34234 Output : False
Enfoque básico: Primero, cree todas las permutaciones de un entero dado y para cada permutación verifique si la permutación es un palíndromo y también divisible por 3. Esto tomará mucho tiempo para crear todas las permutaciones posibles y luego, para cada permutación, verifique si es palíndromo o no. La complejidad temporal para esto es O(n*n!).
Enfoque Eficiente: Se puede observar que para que cualquier número sea un palíndromo, un máximo de un dígito puede tener una frecuencia impar y el resto dígito debe tener una frecuencia par. Además, para que un número sea divisible por 3, la suma de sus dígitos debe ser divisible por 3. Entonces, calcule el dígito y almacene la frecuencia de los dígitos, al calcular el mismo análisis, el resultado puede concluirse fácilmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if any permutation
// of a number is divisible by 3
// and is Palindromic
#include <bits/stdc++.h>
using namespace std;
// Function to check if any permutation
// of a number is divisible by 3
// and is Palindromic
bool isDivisiblePalindrome(int n)
{
// Hash array to store frequency
// of digits of n
int hash[10] = { 0 };
int digitSum = 0;
// traverse the digits of integer
// and store their frequency
while (n) {
// Calculate the sum of
// digits simultaneously
digitSum += n % 10;
hash[n % 10]++;
n /= 10;
}
// Check if number is not
// divisible by 3
if (digitSum % 3 != 0)
return false;
int oddCount = 0;
for (int i = 0; i < 10; i++) {
if (hash[i] % 2 != 0)
oddCount++;
}
// If more than one digits have odd frequency,
// palindromic permutation not possible
if (oddCount > 1)
return false;
else
return true;
}
// Driver Code
int main()
{
int n = 34734;
isDivisiblePalindrome(n) ?
cout << "True" :
cout << "False";
return 0;
}
Java
// Java implementation of the above approach
public class GFG{
// Function to check if any permutation
// of a number is divisible by 3
// and is Palindromic
static boolean isDivisiblePalindrome(int n)
{
// Hash array to store frequency
// of digits of n
int hash[] = new int[10];
int digitSum = 0;
// traverse the digits of integer
// and store their frequency
while (n != 0) {
// Calculate the sum of
// digits simultaneously
digitSum += n % 10;
hash[n % 10]++;
n /= 10;
}
// Check if number is not
// divisible by 3
if (digitSum % 3 != 0)
return false;
int oddCount = 0;
for (int i = 0; i < 10; i++) {
if (hash[i] % 2 != 0)
oddCount++;
}
// If more than one digits have odd frequency,
// palindromic permutation not possible
if (oddCount > 1)
return false;
else
return true;
}
// Driver Code
public static void main(String []args){
int n = 34734;
System.out.print(isDivisiblePalindrome(n)) ;
}
// This code is contributed by ANKITRAI1
}
Python 3
# Python 3 program to check if
# any permutation of a number
# is divisible by 3 and is Palindromic
# Function to check if any permutation
# of a number is divisible by 3
# and is Palindromic
def isDivisiblePalindrome(n):
# Hash array to store frequency
# of digits of n
hash = [0] * 10
digitSum = 0
# traverse the digits of integer
# and store their frequency
while (n) :
# Calculate the sum of
# digits simultaneously
digitSum += n % 10
hash[n % 10] += 1
n //= 10
# Check if number is not
# divisible by 3
if (digitSum % 3 != 0):
return False
oddCount = 0
for i in range(10) :
if (hash[i] % 2 != 0):
oddCount += 1
# If more than one digits have
# odd frequency, palindromic
# permutation not possible
if (oddCount > 1):
return False
else:
return True
# Driver Code
n = 34734
if (isDivisiblePalindrome(n)):
print("True")
else:
print("False")
# This code is contributed
# by ChitraNayal
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to check if any permutation
// of a number is divisible by 3
// and is Palindromic
static bool isDivisiblePalindrome(int n)
{
// Hash array to store frequency
// of digits of n
int []hash = new int[10];
int digitSum = 0;
// traverse the digits of integer
// and store their frequency
while (n != 0)
{
// Calculate the sum of
// digits simultaneously
digitSum += n % 10;
hash[n % 10]++;
n /= 10;
}
// Check if number is not
// divisible by 3
if (digitSum % 3 != 0)
return false;
int oddCount = 0;
for (int i = 0; i < 10; i++)
{
if (hash[i] % 2 != 0)
oddCount++;
}
// If more than one digits have odd frequency,
// palindromic permutation not possible
if (oddCount > 1)
return false;
else
return true;
}
// Driver Code
static public void Main ()
{
int n = 34734;
Console.WriteLine(isDivisiblePalindrome(n));
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program to check if any permutation
// of a number is divisible by 3
// and is Palindromic
// Function to check if any permutation
// of a number is divisible by 3
// and is Palindromic
function isDivisiblePalindrome($n)
{
// Hash array to store frequency
// of digits of n
$hash = array(0 );
$digitSum = 0;
// traverse the digits of integer
// and store their frequency
while ($n) {
// Calculate the sum of
// digits simultaneously
$digitSum += $n % 10;
$hash++;
$n /= 10;
}
// Check if number is not
// divisible by 3
if ($digitSum % 3 != 0)
return false;
$oddCount = 0;
for ($i = 0; $i < 10; $i++)
{
if ($hash % 2 != 0)
$oddCount++;
}
// If more than one digits have odd frequency,
// palindromic permutation not possible
if ($oddCount > 1)
return true;
else
return false;
}
// Driver Code
$n = 34734;
if(isDivisiblePalindrome($n))
echo "True" ;
else
echo "False";
# This Code is contributed by Tushill.
?>
Javascript
<script>
// Javascript program to check if any permutation
// of a number is divisible by 3
// and is Palindromic
// Function to check if any permutation
// of a number is divisible by 3
// and is Palindromic
function isDivisiblePalindrome(n)
{
// Hash array to store frequency
// of digits of n
var hash = Array(10).fill(0);
var digitSum = 0;
// traverse the digits of integer
// and store their frequency
while (n) {
// Calculate the sum of
// digits simultaneously
digitSum += n % 10;
hash[n % 10]++;
n = parseInt(n/10);
}
// Check if number is not
// divisible by 3
if (digitSum % 3 != 0)
return false;
var oddCount = 0;
for (var i = 0; i < 10; i++) {
if (hash[i] % 2 != 0)
oddCount++;
}
// If more than one digits have odd frequency,
// palindromic permutation not possible
if (oddCount > 1)
return false;
else
return true;
}
// Driver Code
var n = 34734;
isDivisiblePalindrome(n) ?
document.write( "True" ):
document.write( "False");
</script>
Producción:
True
Complejidad de tiempo : O(n), donde n es el número de dígitos en el número dado.
Espacio Auxiliar: O(10)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA