Comprueba si un número dado se puede representar en un no dado. de dígitos en cualquier base

Dado un número y no. de dígitos para representar el número, encuentre si el número dado se puede representar en el número dado. de dígitos en cualquier base del 2 al 32.
Ejemplos: 
 

Input: 8 4  
Output: Yes
Possible in base 2 as 8 in base 2 is 1000

Input: 8 2 
Output: Yes 
Possible in base 3 as 8 in base 3 is 22

Input: 8 3  
Output: No
Not possible in any base

Le recomendamos encarecidamente que minimice su navegador y pruebe esto usted mismo primero.
La idea es verificar todas las bases una por una desde la base 2 hasta la base 32. ¿Cómo verificamos una base dada? Los siguientes son pasos simples. 
1) SI el número es más pequeño que la base y el dígito es 1, entonces devuelve verdadero. 
2) De lo contrario, si el dígito es mayor que 1 y el número es mayor que la base, elimine el último dígito de num haciendo num/base, reduzca la cantidad de dígitos y recurra. 
3) De lo contrario, devuelve falso
. A continuación se muestra la implementación de la idea anterior. 
 

C++

// C++ program to check if a given number can be
// represented in given number of digits in any base
#include <iostream>
using namespace std;
 
// Returns true if 'num' can be represented using 'dig'
// digits in 'base'
bool checkUtil(int num, int dig, int base)
{
    // Base case
    if (dig==1 && num < base)
       return true;
 
    // If there are more than 1 digits left and number
    // is more than base, then remove last digit by doing
    // num/base, reduce the number of digits and recur
    if (dig > 1 && num >= base)
       return checkUtil(num/base, --dig, base);
 
    return false;
}
 
// return true of num can be represented in 'dig'
// digits in any base from 2 to 32
bool check(int num, int dig)
{
    // Check for all bases one by one
    for (int base=2; base<=32; base++)
       if (checkUtil(num, dig, base))
            return true;
    return false;
}
 
// Driver program
int main()
{
    int num = 8;
    int dig = 3;
    (check(num, dig))? cout << "Yes" : cout << "No";
    return 0;
}

Java

// Java program to check if a
// given number can be represented
// in given number of digits in any base
class GFG
{
    // Returns true if 'num' can be
    // represented using 'dig' digits in 'base'
    static boolean checkUtil(int num, int dig, int base)
    {
        // Base case
        if (dig==1 && num < base)
        return true;
     
        // If there are more than 1 digits
        // left and number is more than base,
        // then remove last digit by doing num/base,
        //  reduce the number of digits and recur
        if (dig > 1 && num >= base)
        return checkUtil(num / base, --dig, base);
     
        return false;
    }
     
    // return true of num can be
    // represented in 'dig' digits
    // in any base from 2 to 32
    static boolean check(int num, int dig)
    {
        // Check for all bases one by one
        for (int base = 2; base <= 32; base++)
        if (checkUtil(num, dig, base))
                return true;
        return false;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int num = 8;
        int dig = 3;
        if(check(num, dig))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python program to check
# if a given number can be
# represented in given number
# of digits in any base
 
# Returns true if 'num' can
# be represented using 'dig'
# digits in 'base'
def checkUtil(num,dig,base):
     
    # Base case
    if (dig==1 and num < base):
        return True
  
    # If there are more than 1
    # digits left and number
    # is more than base, then
    # remove last digit by doing
    # num/base, reduce the number
    # of digits and recur
    if (dig > 1 and num >= base):
        return checkUtil(num/base, --dig, base)
  
    return False
  
# return true of num can
# be represented in 'dig'
# digits in any base from 2 to 32
def check(num,dig):
 
    # Check for all bases one by one
    for base in range(2,33):
 
        if (checkUtil(num, dig, base)):
            return True
    return False
 
# driver code
num = 8
dig = 3
if(check(num, dig)==True):
    print("Yes")
else:
    print("No")
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program to check if a given
// number can be represented in
// given number of digits in any base
using System;
 
class GFG {
     
    // Returns true if 'num' can be
    // represented using 'dig' digits
    // in 'base'
    static bool checkUtil(int num, int dig,
                          int i)
    {
         
        // Base case
        if (dig == 1 && num < i)
        return true;
     
        // If there are more than 1 digits
        // left and number is more than base,
        // then remove last digit by doing
        // num/base, reduce the number of
        // digits and recur
        if (dig > 1 && num >= i)
        return checkUtil((num / i), --dig, i);
     
        return false;
    }
     
    // return true of num can be
    // represented in 'dig' digits
    // in any base from 2 to 32
    static bool check(int num, int dig)
    {
         
        // Check for all bases one by one
        for (int i = 2; i <= 32; i++)
        if (checkUtil(num, dig, i))
                return true;
        return false;
    }
     
    // Driver code
    public static void Main()
    {
        int num = 8;
        int dig = 3;
        if(check(num, dig))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// PHP program to check if a given
// number can be represented in given
// number of digits in any base
 
// Returns true if 'num' can be
// represented using 'dig'
// digits in 'base'
 
function checkUtil($num, $dig, $base)
{
    // Base case
    if ($dig == 1 && $num < $base)
    return true;
 
    // If there are more than 1
    // digits left and number is
    // more than base, then remove
    // last digit by doing num/base,
    // reduce the number of digits and recur
    if ($dig > 1 && $num >= $base)
    return checkUtil($num / $base,
                   --$dig, $base);
 
    return false;
}
 
// return true of num can be
// represented in 'dig' digits
// in any base from 2 to 32
function check($num, $dig)
{
    // Check for all bases one by one
    for ($base = 2; $base <= 32; $base++)
    if (checkUtil($num, $dig, $base))
            return true;
    return false;
}
 
// Driver Code
$num = 8;
$dig = 3;
if (check($num, $dig) == true)
echo "Yes" ;
else
echo "No";
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// javascript program to check if a
// given number can be represented
// in given number of digits in any base
 
    // Returns true if 'num' can be
    // represented using 'dig' digits in 'base'
    function checkUtil(num , dig , base)
    {
        // Base case
        if (dig == 1 && num < base)
            return true;
 
        // If there are more than 1 digits
        // left and number is more than base,
        // then remove last digit by doing num/base,
        // reduce the number of digits and recur
        if (dig > 1 && num >= base)
            return checkUtil(parseInt(num / base), --dig, base);
 
        return false;
    }
 
    // return true of num can be
    // represented in 'dig' digits
    // in any base from 2 to 32
    function check(num , dig) {
        // Check for all bases one by one
        for (base = 2; base <= 32; base++)
            if (checkUtil(num, dig, base))
                return true;
        return false;
    }
 
    // Driver code
     
        var num = 8;
        var dig = 3;
        if (check(num, dig))
            document.write("Yes");
        else
            document.write("No");
 
// This code contributed by Rajput-Ji
 
</script>

Producción : 

No

Complejidad de tiempo: O (32 * 32)

Espacio auxiliar: O(1)
Este artículo es una contribución de Mehboob Elahi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *