Compruebe si N contiene todos los dígitos como K en la base B

Posted on by Rudeus Greyrat

Dados tres números N , K y B , la tarea es verificar si N contiene solo K como dígitos en la Base B .

Ejemplos: 

Entrada: N = 13, B = 3, K = 1 
Salida: Sí
Explicación: 
13 base 3 es 111 que contiene todos los uno (K).

Entrada: N = 5, B = 2, K = 1 
Salida: No 
Explicación:
5 base 2 es 101 que no contiene todos los unos (K).

Enfoque ingenuo: una solución simple es convertir el número N dado a la base B y verificar uno por uno si todos sus dígitos son K o no.
Complejidad de tiempo: O(D), donde D es el número de dígitos en el número N 
Espacio auxiliar: O(1)

Enfoque eficiente: la observación clave en el problema es que cualquier número con todos los dígitos como K en base B se puede representar como:

K*B^0 + K*B^1 + K*B^2+...K*B^{\log_b N + 1} = N

Estos términos tienen la forma de progresión geométrica con el primer término como K y la razón común como B.

Suma de la Serie GP:

\frac{a * (1 - r^{N})}{(1-r)}

Por lo tanto, el número en base B con todos los dígitos como K es:

\frac{K * (1-B^{log_bN + 1})}{(1-B)}

Por lo tanto, solo verifique si esta suma es igual a N o no. Si es igual, escriba «Sí», de lo contrario, escriba «No» .
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to print the number of digits
int findNumberOfDigits(int n, int base)
{
     
    // Calculate log using base change
    // property and then take its floor
    // and then add 1
    int dig = (floor(log(n) / log(base)) + 1);
 
    // Return the output
    return (dig);
}
 
// Function that returns true if n contains
// all one's in base b
int isAllKs(int n, int b, int k)
{
    int len = findNumberOfDigits(n, b);
 
    // Calculate the sum
    int sum = k * (1 - pow(b, len)) /
                  (1 - b);
    if(sum == n)
    {
        return(sum);
    }
}
 
// Driver code
int main()
{
     
    // Given number N
    int N = 13;
     
    // Given base B
    int B = 3;
     
    // Given digit K
    int K = 1;
     
    // Function call
    if (isAllKs(N, B, K))
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}
 
// This code is contributed by vikas_g

C

// C implementation of the approach
#include <stdio.h>
#include <math.h>
 
// Function to print the number of digits
int findNumberOfDigits(int n, int base)
{
     
    // Calculate log using base change
    // property and then take its floor
    // and then add 1
    int dig = (floor(log(n) / log(base)) + 1);
 
    // Return the output
    return (dig);
}
 
// Function that returns true if n contains
// all one's in base b
int isAllKs(int n, int b, int k)
{
    int len = findNumberOfDigits(n, b);
 
    // Calculate the sum
    int sum = k * (1 - pow(b, len)) /
                  (1 - b);
    if(sum == n)
    {
        return(sum);
    }
}
 
// Driver code
int main(void)
{
     
    // Given number N
    int N = 13;
     
    // Given base B
    int B = 3;
     
    // Given digit K
    int K = 1;
     
    // Function call
    if (isAllKs(N, B, K))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}
 
// This code is contributed by vikas_g

Java

// Java implementation of above approach
import java.util.*;
 
class GFG{
 
// Function to print the number of digits
static int findNumberOfDigits(int n, int base)
{
     
    // Calculate log using base change
    // property and then take its floor
    // and then add 1
    int dig = ((int)Math.floor(Math.log(n) /
                    Math.log(base)) + 1);
     
    // Return the output
    return dig;
}
 
// Function that returns true if n contains
// all one's in base b
static boolean isAllKs(int n, int b, int k)
{
    int len = findNumberOfDigits(n, b);
     
    // Calculate the sum
    int sum = k * (1 - (int)Math.pow(b, len)) /
                  (1 - b);
     
    return sum == n;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given number N
    int N = 13;
     
    // Given base B
    int B = 3;
     
    // Given digit K
    int K = 1;
     
    // Function call
    if (isAllKs(N, B, K))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
import math
 
# Function to print the number of digits
def findNumberOfDigits(n, base):
 
    # Calculate log using base change
    # property and then take its floor
    # and then add 1
    dig = (math.floor(math.log(n) /
                      math.log(base)) + 1)
 
    # Return the output
    return dig
 
# Function that returns true if n contains
# all one's in base b
def isAllKs(n, b, k):
 
    len = findNumberOfDigits(n, b)
 
    # Calculate the sum
    sum = k * (1 - pow(b, len)) / (1 - b)
 
    return sum == N
 
# Driver code
 
# Given number N
N = 13
 
# Given base B
B = 3
 
# Given digit K
K = 1
 
# Function call
if (isAllKs(N, B, K)):
    print("Yes")
else:
    print("No")

C#

// C# implementation of above approach
using System;
 
class GFG{
     
// Function to print the number of digits
static int findNumberOfDigits(int n, int bas)
{
     
    // Calculate log using base change
    // property and then take its floor
    // and then add 1
    int dig = ((int)Math.Floor(Math.Log(n) /
                               Math.Log(bas)) + 1);
     
    // Return the output
    return dig;
}
 
// Function that returns true if n contains
// all one's in base b
static bool isAllKs(int n, int b, int k)
{
    int len = findNumberOfDigits(n, b);
     
    // Calculate the sum
    int sum = k * (1 - (int)Math.Pow(b, len)) /
                  (1 - b);
     
    return sum == n;
}
 
// Driver code
public static void Main()
{
     
    // Given number N
    int N = 13;
     
    // Given base B
    int B = 3;
     
    // Given digit K
    int K = 1;
     
    // Function call
    if (isAllKs(N, B, K))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by vikas_g

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to print the number of digits
function findNumberOfDigits(n, base)
{
     
    // Calculate log using base change
    // property and then take its floor
    // and then add 1
    var dig = (Math.floor(Math.log(n) / Math.log(base)) + 1);
 
    // Return the output
    return (dig);
}
 
// Function that returns true if n contains
// all one's in base b
function isAllKs(n, b, k)
{
    var len = findNumberOfDigits(n, b);
 
    // Calculate the sum
    var sum = k * (1 - Math.pow(b, len)) /
                  (1 - b);
    if(sum == n)
    {
        return(sum);
    }
}
 
// Driver code
// Given number N
var N = 13;
 
// Given base B
var B = 3;
 
// Given digit K
var K = 1;
 
// Function call
if (isAllKs(N, B, K))
{
    document.write( "Yes");
}
else
{
    document.write("No");
}
 
// This code is contributed by rrrtnx.
</script>
Producción: 

Yes

Complejidad de tiempo: O(log(D)), donde D es el número de dígitos en el número N  
Espacio auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por spp____ 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 *