Comprueba si alguna permutación de N es igual a alguna potencia de K

Dado un entero positivo N y K donde

$2 \leq N \leq 10^{18}$

$2 \leq K \leq N$

. La tarea es comprobar si alguna permutación de dígitos de N es igual a alguna potencia de K. Si es posible, devuelva » Verdadero «, de lo contrario, devuelva » Falso «.
Ejemplos:

Input: N = 96889010407, K = 7
Output: True
Explanation: 96889010407 = 7¹³

Input : N = 123456789, K = 4
Output : False

Enfoque: el enfoque Naive es generar todas las permutaciones de dígitos de N y luego verificar uno por uno si alguno de ellos es divisible de alguna potencia de K.
Enfoque eficiente: sabemos que los números totales de todas las potencias de K no serán más que log _K (10 ¹⁸ ) , por ejemplo: si K = 2 , habrá como máximo 64 números de potencias de K . Generamos todo el poder de K y lo almacenamos en una array.
Ahora iteramos todos los números de la array y verificamos dónde contiene todos los dígitos de N o no.
A continuación se muestra la implementación del enfoque anterior:

C++

// CPP implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to check if N and K are anagrams
bool isValid(long long int N, long long int K)
{
    multiset<int> m1, m2;
 
    while (N > 0) {
        m1.insert(N % 10);
        N /= 10;
    }
 
    while (K > 0) {
        m2.insert(K % 10);
        K /= 10;
    }
 
    if (m1 == m2)
        return true;
    return false;
}
 
// Function to check if any permutation of N exist
// such that it is some power of K
string anyPermutation(long long int N, long long int K)
{
    long long int powK[100], Limit = pow(10, 18);
 
    // generate all power of K under 10^18
    powK[0] = K;
 
    int i = 1;
    while (powK[i - 1] * K < Limit) {
        powK[i] = powK[i - 1] * K;
        i++;
    }
 
    // check if any power of K is valid
    for (int j = 0; j < i; j++)
        if (isValid(N, powK[j])) {
            return "True";
        }
 
    return "False";
}
 
// Driver program
int main()
{
    long long int N = 96889010407, K = 7;
 
    // function call to print required answer
    cout << anyPermutation(N, K);
 
    return 0;
}
 
// This code is written by Sanjit_Prasad

Java

// Java implementation of above approach.
import java.util.*;
 
class GfG
{
 
    // function to check if N and K are anagrams
    static boolean isValid(int N, int K)
    {
        HashSet<Integer> m1 = new HashSet<Integer>();
        HashSet<Integer> m2 = new HashSet<Integer>();
        while (N > 0)
        {
            m1.add(N % 10);
            N /= 10;
        }
 
        while (K > 0)
        {
            m2.add(K % 10);
            K /= 10;
        }
 
        if (m1.equals(m2))
        {
            return true;
        }
        return false;
    }
 
    // Function to check if any
    // permutation of N exist
    // such that it is some power of K
    static String anyPermutation(int N, int K)
    {
        int powK[] = new int[100 + 1], Limit = (int) Math.pow(10, 18);
 
        // generate all power of K under 10^18
        powK[0] = K;
 
        int i = 1;
        while (powK[i - 1] * K < Limit && i<100)
        {
            powK[i] = powK[i - 1] * K;
            i++;
        }
 
        // check if any power of K is valid
        for (int j = 0; j < i; j++)
        {
            if (isValid(N, powK[j]))
            {
                return "True";
            }
        }
 
        return "False";
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = (int) 96889010407L, K = 7;
 
        // function call to print required answer
        System.out.println(anyPermutation(N, K));
    }
}
 
// This code contributed by Rajput-Ji

Python 3

# Python 3 implementation of above approach
 
# function to check if N
# and K are anagrams
def isValid(N, K):
 
    m1 = []
    m2 = []
 
    while (N > 0) :
        m1.append(N % 10)
        N //= 10
 
    while (K > 0) :
        m2.append(K % 10)
        K //= 10
 
    if (m1 == m2):
        return True
    return False
 
# Function to check if any permutation
# of N exist such that it is some power of K
def anyPermutation(N, K):
 
    powK = [0] * 100
    Limit = pow(10, 18)
 
    # generate all power of
    # K under 10^18
    powK[0] = K
 
    i = 1
    while (powK[i - 1] * K < Limit) :
        powK[i] = powK[i - 1] * K
        i += 1
 
    # check if any power of K is valid
    for j in range(i):
        if (isValid(N, powK[j])) :
            return "True"
 
    return "False"
 
# Driver Code
if __name__ == "__main__":
 
    N = 96889010407
    K = 7
 
    # function call to print
    # required answer
    print(anyPermutation(N, K))
 
# This code is contributed
# by ChitraNayal

C#

// C# implementation of above approach.
using System;
using System.Collections.Generic;
class GfG{
 
// Function to check if N and K are anagrams
static bool isValid(long N, int K)
{
  HashSet<long> m1 = new HashSet<long>();
  HashSet<int> m2 = new HashSet<int>();
  while (N > 0)
  {
    m1.Add(N % 10);
    N /= 10;
  }
 
  while (K > 0)
  {
    m2.Add(K % 10);
    K /= 10;
  }
 
  if (m1.Equals(m2))
  {
    return true;
  }
  return false;
}
 
// Function to check if any
// permutation of N exist
// such that it is some power of K
static String anyPermutation(long N,
                             int K)
{
  int []powK = new int[100 + 1];
  int Limit = (int) Math.Pow(10, 18);
 
  // Generate all power
  // of K under 10^18
  powK[0] = K;
 
  int i = 1;
  while (powK[i - 1] * K < Limit && i < 100)
  {
    powK[i] = powK[i - 1] * K;
    i++;
  }
 
  // Check if any power of K is valid
  for (int j = 0; j < i; j++)
  {
    if (!isValid(N, powK[j]))
    {
      return "True";
    }
  }
 
  return "False";
}
 
// Driver code
public static void Main(String[] args)
{
  long N = 96889010407;
  int K = 7;
 
  // Function call to print required answer
  Console.WriteLine(anyPermutation(N, K));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// Javascript implementation of above approach.
 
// function to check if N and K are anagrams
function isValid(N,K)
{
        let m1 = new Set();
        let m2 = new Set();
        while (N > 0)
        {
            m1.add(N % 10);
            N = Math.floor(N/10);
        }
  
        while (K > 0)
        {
            m2.add(K % 10);
            K = Math.floor(K/10);
        }
          
        // To check both set are equal or not
        let s = new Set([...m1, ...m2])
        return s.size == m1.size && s.size == m2.size
}
 
// Function to check if any
    // permutation of N exist
    // such that it is some power of K
function anyPermutation(N,K)
{
    let powK = new Array(100 + 1), Limit = (Math.pow(10, 18));
         for(let i=0;i<101;i++)
            powK[i]=0;
        // generate all power of K under 10^18
        powK[0] = K;
  
        let i = 1;
        while (powK[i - 1] * K < Limit )
        {
            powK[i] = powK[i - 1] * K;
             
            i++;
        }
          
        // check if any power of K is valid
        for (let j = 0; j < i; j++)
        {
             
            if (isValid(N, powK[j]))
            {
                return "True";
            }
        }
  
        return "False";
}
 
// Driver code
let N =  96889010407, K = 7;
 
// function call to print required answer
document.write(anyPermutation(N, K));
 
// This code is contributed by patel2127
</script>

Producción:

True

Complejidad del tiempo: O(log _K (10 ¹⁸ ) ² )

Espacio Auxiliar: O(log ₁₀ N + log ₁₀ K)

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python 3

C#

Javascript

Deja una respuesta Cancelar la respuesta