Dado un número entero N, la tarea es verificar si alguna permutación de N sin ceros a la izquierda es una potencia de 2. Si existe tal permutación del número dado, imprima esa permutación. De lo contrario , imprima No.
Ejemplos:
Entrada: N = 46
Salida: 64
Explicación:
La permutación de 46 que es potencia perfecta de 2 es 64( = 2 6 )Entrada: N = 75
Salida: No
Explicación:
No hay una permutación posible de 75 que resulte en una potencia perfecta de 2.
Enfoque ingenuo: una solución simple es generar todas las permutaciones del número N y, para cada permutación, verificar si es una potencia de 2 o no. Si se encuentra que es cierto, escriba Sí . De lo contrario , imprima No.
Complejidad de tiempo: O( (log 10 N )!*(log 10 N)), donde N es el número dado N.
Espacio auxiliar: O(1)
Enfoque eficiente: el recuento de dígitos para el número dado y para cualquier permutación del número dado siempre será el mismo. Por lo tanto, para optimizar el enfoque anterior, simplemente verifique si la cantidad de dígitos del número dado es igual a cualquier potencia perfecta de 2 o no. Si es cierto, imprima esa potencia de 2. De lo contrario, imprima No.
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;
const int TEN = 10;
// Function to update the frequency
// array such that freq[i] stores
// the frequency of digit i to n
void updateFreq(int n, int freq[])
{
// While there are digits
// left to process
while (n) {
int digit = n % TEN;
// Update the frequency of
// the current digit
freq[digit]++;
// Remove the last digit
n /= TEN;
}
}
// Function that returns true if a
// and b are anagrams of each other
bool areAnagrams(int a, int b)
{
// To store the frequencies of
// the digits in a and b
int freqA[TEN] = { 0 };
int freqB[TEN] = { 0 };
// Update the frequency of
// the digits in a
updateFreq(a, freqA);
// Update the frequency of
// the digits in b
updateFreq(b, freqB);
// Match the frequencies of
// the common digits
for (int i = 0; i < TEN; i++) {
// If frequency differs for any
// digit then the numbers are
// not anagrams of each other
if (freqA[i] != freqB[i])
return false;
}
return true;
}
// Function to check if any permutation
// of a number is a power of 2 or not
bool isPowerOf2(int N)
{
// Iterate over all possible perfect
// power of 2
for (int i = 0; i < 32; i++) {
if (areAnagrams(1 << i, N)) {
// Print that number
cout << (1 << i);
return true;
}
}
return false;
}
// Driver Code
int main()
{
// Given Number N
int N = 46;
// Function Call
if (!isPowerOf2(N)) {
cout << "No";
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int TEN = 10;
// Function to update the frequency
// array such that freq[i] stores
// the frequency of digit i to n
static void updateFreq(int n, int freq[])
{
// While there are digits
// left to process
while (n > 0)
{
int digit = n % TEN;
// Update the frequency of
// the current digit
freq[digit]++;
// Remove the last digit
n /= TEN;
}
}
// Function that returns true if a
// and b are anagrams of each other
static boolean areAnagrams(int a, int b)
{
// To store the frequencies of
// the digits in a and b
int freqA[] = new int[TEN];
int freqB[] = new int[TEN];
// Update the frequency of
// the digits in a
updateFreq(a, freqA);
// Update the frequency of
// the digits in b
updateFreq(b, freqB);
// Match the frequencies of
// the common digits
for(int i = 0; i < TEN; i++)
{
// If frequency differs for any
// digit then the numbers are
// not anagrams of each other
if (freqA[i] != freqB[i])
return false;
}
return true;
}
// Function to check if any permutation
// of a number is a power of 2 or not
static boolean isPowerOf2(int N)
{
// Iterate over all possible perfect
// power of 2
for(int i = 0; i < 32; i++)
{
if (areAnagrams(1 << i, N))
{
// Print that number
System.out.print((1 << i));
return true;
}
}
return false;
}
// Driver Code
public static void main(String[] args)
{
// Given number N
int N = 46;
// Function call
if (!isPowerOf2(N))
{
System.out.print("No");
}
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
TEN = 10
# Function to update the frequency
# array such that freq[i] stores
# the frequency of digit i to n
def updateFreq(n, freq):
# While there are digits
# left to process
while (n):
digit = n % TEN
# Update the frequency of
# the current digit
freq[digit] += 1
# Remove the last digit
n //= TEN
# Function that returns true if a
# and b are anagrams of each other
def areAnagrams(a, b):
# To store the frequencies of
# the digits in a and b
freqA = [0] * (TEN)
freqB = [0] * (TEN)
# Update the frequency of
# the digits in a
updateFreq(a, freqA)
# Update the frequency of
# the digits in b
updateFreq(b, freqB)
# Match the frequencies of
# the common digits
for i in range(TEN):
# If frequency differs for any
# digit then the numbers are
# not anagrams of each other
if (freqA[i] != freqB[i]):
return False
return True
# Function to check if any permutation
# of a number is a power of 2 or not
def isPowerOf2(N):
# Iterate over all possible perfect
# power of 2
for i in range(32):
if (areAnagrams(1 << i, N)):
# Print that number
print(1 << i)
return True
return False
# Driver Code
# Given number N
N = 46
# Function call
if (isPowerOf2(N) == 0):
print("No")
# This code is contributed by code_hunt
C#
// C# program for
// the above approach
using System;
class GFG{
static int TEN = 10;
// Function to update the frequency
// array such that freq[i] stores
// the frequency of digit i to n
static void updateFreq(int n,
int []freq)
{
// While there are digits
// left to process
while (n > 0)
{
int digit = n % TEN;
// Update the frequency of
// the current digit
freq[digit]++;
// Remove the last digit
n /= TEN;
}
}
// Function that returns true if a
// and b are anagrams of each other
static bool areAnagrams(int a, int b)
{
// To store the frequencies of
// the digits in a and b
int []freqA = new int[TEN];
int []freqB = new int[TEN];
// Update the frequency of
// the digits in a
updateFreq(a, freqA);
// Update the frequency of
// the digits in b
updateFreq(b, freqB);
// Match the frequencies of
// the common digits
for(int i = 0; i < TEN; i++)
{
// If frequency differs for any
// digit then the numbers are
// not anagrams of each other
if (freqA[i] != freqB[i])
return false;
}
return true;
}
// Function to check if any
// permutation of a number
// is a power of 2 or not
static bool isPowerOf2(int N)
{
// Iterate over all
// possible perfect power of 2
for(int i = 0; i < 32; i++)
{
if (areAnagrams(1 << i, N))
{
// Print that number
Console.Write((1 << i));
return true;
}
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
// Given number N
int N = 46;
// Function call
if (!isPowerOf2(N))
{
Console.Write("No");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
var TEN = 10;
// Function to update the frequency
// array such that freq[i] stores
// the frequency of digit i to n
function updateFreq(n, freq)
{
// While there are digits
// left to process
while (n) {
var digit = n % TEN;
// Update the frequency of
// the current digit
freq[digit]++;
// Remove the last digit
n = parseInt(n/TEN);
}
}
// Function that returns true if a
// and b are anagrams of each other
function areAnagrams(a, b)
{
// To store the frequencies of
// the digits in a and b
var freqA = Array(TEN).fill(0);
var freqB = Array(TEN).fill(0);
// Update the frequency of
// the digits in a
updateFreq(a, freqA);
// Update the frequency of
// the digits in b
updateFreq(b, freqB);
// Match the frequencies of
// the common digits
for (var i = 0; i < TEN; i++) {
// If frequency differs for any
// digit then the numbers are
// not anagrams of each other
if (freqA[i] != freqB[i])
return false;
}
return true;
}
// Function to check if any permutation
// of a number is a power of 2 or not
function isPowerOf2(N)
{
// Iterate over all possible perfect
// power of 2
for (var i = 0; i < 32; i++) {
if (areAnagrams(1 << i, N)) {
// Print that number
document.write( (1 << i));
return true;
}
}
return false;
}
// Driver Code
// Given Number N
var N = 46;
// Function Call
if (!isPowerOf2(N)) {
document.write( "No");
}
</script>
Producción:
64
Complejidad de Tiempo: O((log 10 N) 2 )
Espacio Auxiliar: O(1)