Trucos de logaritmos para la programación competitiva

Logaritmo : es la función inversa de la exponenciación, lo que significa que el valor del logaritmo de un número dado x es el exponente de otro número.
$log_b(x) = y, \to b^{y} = x$

A continuación hay algunos trucos que usan la función logarítmica que pueden ser útiles en la programación competitiva.

Comprobando si un número es una potencia de dos o no:

Dado un número entero N , la tarea es comprobar si el número N es la potencia de 2.

Ejemplos:

Entrada: N = 8
Salida: Sí

Entrada: N = 6
Salida: No

Enfoque: un método simple para esto es simplemente tomar el registro del número en base 2, si obtiene un número entero, entonces el número es la potencia de 2.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation to check that
// a integer is a power of Two
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to check if the number
// is a power of two
bool isPowerOfTwo(int n)
{
    return (ceil(log2(n)) == floor(log2(n)));
}
 
// Driver Code
int main()
{
    int N = 8;
 
    if (isPowerOfTwo(N)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

C

// C implementation to check that
// a integer is a power of Two
#include <stdio.h>
#include <math.h>
 
// Function to check if the number
// is a power of two
_Bool isPowerOfTwo(int n)
{
    return (ceil(log2(n)) == floor(log2(n)));
}
 
// Driver Code
int main()
{
    int N = 8;
 
    if (isPowerOfTwo(N))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
}
 
// This code is contributed by vikas_g

Java

// Java implementation to check that
// a integer is a power of Two
import java.lang.Math;
 
class GFG{
     
// Function to check if the number
// is a power of two
public static boolean isPowerOfTwo(int n)
{
    return(Math.ceil(Math.log(n) /
                     Math.log(2)) ==
          Math.floor(Math.log(n) /
                     Math.log(2)));
}
     
// Driver Code
public static void main(String[] args)
{
    int N = 8;
 
    if (isPowerOfTwo(N))
    {
        System.out.println("Yes");
    }
    else
    {
        System.out.println("No");
    }
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 implementation to check that
# a integer is a power of two
import math
 
# Function to check if the number
# is a power of two            
def isPowerOfTwo(n):
     
    return(math.ceil(math.log(n) //
                     math.log(2)) ==
           math.floor(math.log(n) //
                      math.log(2)));
                     
# Driver code
if __name__=='__main__':
     
    N = 8
     
    if isPowerOfTwo(N):
        print('Yes')
    else:
        print('No')
 
# This code is contributed by rutvik_56

C#

// C# implementation to check that
// a integer is a power of Two
using System;
 
class GFG{
     
// Function to check if the number
// is a power of two
public static bool isPowerOfTwo(int n)
{
    return(Math.Ceiling(Math.Log(n) /
                        Math.Log(2)) ==
             Math.Floor(Math.Log(n) /
                        Math.Log(2)));
}
     
// Driver Code
public static void Main(String[] args)
{
    int N = 8;
 
    if (isPowerOfTwo(N))
    {
        Console.WriteLine("Yes");
    }
    else
    {
        Console.WriteLine("No");
    }
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
    // Java implementation to check that
      // a integer is a power of Two
     
    // Function to check if the number
    // is a power of two
    function isPowerOfTwo(n)
    {
        return (Math.ceil(Math.log(n) / Math.log(2)) == Math.floor(Math.log(n) / Math.log(2)));
    }
      
    let N = 8;
   
    if (isPowerOfTwo(N)) {
        document.write("Yes");
    }
    else {
        document.write("No");
    }
     
    // This code is contributed by Shubham.
</script>

Producción:

Yes

K-ésima raíz de un número

Dados dos enteros N y K , la tarea es encontrar la raíz K ^-ésima del número N.

Ejemplos:

Entrada: N = 8, K = 3
Salida: 2

Entrada: N = 32, K = 5
Salida: 2

Enfoque: una solución simple es usar la función logarítmica para encontrar la raíz K ^-ésima del número. A continuación se muestra la ilustración del enfoque:

Sea D nuestra respuesta
entonces, $N^{(\frac{1}{K})} = D$
aplicando $Log_K$ en ambos lados
=> $Log_K(N^{(\frac{1}{K})}) = Log_{K}(D)$
=> $(\frac{1}{K}) * Log_K(N) = Log_{K}(D)$
=> $D = K^{(\frac{1}{K}) * Log_K(N)}$

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation to find
// Kth root of the number
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the
// Kth root of the number
double kthRoot(double n, int k)
{
    return pow(k,
               (1.0 / k)
                   * (log(n)
                      / log(k)));
}
 
// Driver Code
int main()
{
    double N = 8.0;
    int K = 3;
 
    cout << kthRoot(N, K);
 
    return 0;
}

Java

// Java implementation to find
// Kth root of the number
class GFG{
 
// Function to find the
// Kth root of the number
static double kthRoot(double n, int k)
{
    return Math.pow(k, (1.0 / k) *
                    (Math.log(n) / Math.log(k)));
}
 
// Driver Code
public static void main(String[] args)
{
    double N = 8.0;
    int K = 3;
 
    System.out.print(kthRoot(N, K));
}
}
 
// This code is contributed by shivanisinghss2110

Python3

# Python3 implementation to find
# Kth root of the number
import math
 
# Function to find the
# Kth root of the number
def kth_root(n, k):
     
    return(pow(k, ((1.0 / k) * (math.log(n) /
                                math.log(k)))))
 
# Driver code
if __name__=="__main__":
     
    n = 8.0
    k = 3
     
    print(round(kth_root(n, k)))
 
# This code is contributed by dipesh99kumar

C#

// C# implementation to find
// Kth root of the number
using System;
 
// Function to find the
// Kth root of the number
class GFG{
     
static double kthRoot(double n, int k)
{
    return Math.Pow(k, (1.0 / k) *
                   (Math.Log(n) / Math.Log(k)));
}
 
// Driver Code
public static void Main()
{
    double N = 8.0;
    int K = 3;
 
    Console.Write(kthRoot(N, K));
}
}
 
// This code is contributed by vikas_g

Javascript

<script>
 
// Javascript implementation to find
// Kth root of the number
 
// Function to find the
// Kth root of the number
function kthRoot(n, k)
{
    return Math.pow(k,
               (1.0 / k)
                   * (Math.log(n)
                      / Math.log(k)));
}
 
// Driver Code
var N = 8.0;
var K = 3;
document.write( kthRoot(N, K));
 
</script>

Producción:

Contar dígitos en un número:

Dado un número entero N , la tarea es contar los dígitos de un número N.

Ejemplos:

Entrada: N = 243
Salida: 3

Entrada: N = 1000
Salida: 4

Planteamiento: La idea es encontrar el logaritmo del número base 10 para contar el número de dígitos.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation count the
// number of digits in a number
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to count the
// number of digits in a number
int countDigit(long long n)
{
    return floor(log10(n) + 1);
}
 
// Driver Code
int main()
{
    double N = 80;
 
    cout << countDigit(N);
 
    return 0;
}

C

// C implementation count the
// number of digits in a number
#include <stdio.h>
#include <math.h>
 
// Function to count the
// number of digits in a number
int countDigit(long long n)
{
    return (floor(log10(n) + 1));
}
 
// Driver Code
int main()
{
    double N = 80;
 
    printf("%d", countDigit(N));
 
    return 0;
}
 
// This code is contributed by vikas_g

Java

// Java implementation to count the
// number of digits in a number
class GFG{
 
// Function to count the
// number of digits in a number
static int countDigit(double n)
{
    return((int)Math.floor(Math.log10(n) + 1));
 
}
 
// Driver Code
public static void main(String[] args)
{
    double N = 80;
     
    System.out.println(countDigit(N));
}
}
 
// This code is contributed by vikas_g

Python3

# Python3 implementation count the
# number of digits in a number
import math
 
# Function to count the
# number of digits in a number
def countDigit(n):
     
    return(math.floor(math.log10(n) + 1))
 
# Driver code
if __name__=="__main__":
     
    n = 80
 
    print(countDigit(n))
 
# This code is contributed by dipesh99kumar

C#

// C# implementation count the
// number of digits in a number
using System;
 
// Function to count the
// number of digits in a number
class GFG{
     
static int countDigit(double n)
{
    return((int)Math.Floor(Math.Log10(n) + 1));
}
 
// Driver Code
public static void Main()
{
    double N = 80;
     
    Console.Write(countDigit(N));
}
}
 
// This code is contributed by vikas_g

Javascript

<script>
//Javascript implementation
 
// Function to count the
// number of digits in a number
function countDigit(n)
{
    return Math.floor(Math.log10(n) + 1);
}
 
// Driver program to test above
var n = 80;
document.write(countDigit(n));
// This code is contributed by shivani.
</script>

Producción:

Comprueba si N es una potencia de K o no:

Dados dos números enteros N y K , la tarea es verificar si Y es potencia de X o no.

Ejemplos:

Entrada: N = 8, K = 2
Salida: Sí

Entrada: N = 27, K = 3
Salida: Sí

Enfoque: La idea es sacar logaritmo de N en base K. Si resulta ser un número entero, entonces N es una potencia de K.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation to check if
// the number is power of K
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to check if
// the number is power of K
bool isPower(int N, int K)
{
    // logarithm function to
    // calculate value
    int res1 = log(N) / log(K);
    double res2 = log(N) / log(K);
 
    // compare to the result1
    // or result2 both are equal
    return (res1 == res2);
}
 
// Driver Code
int main()
{
    int N = 8;
    int K = 2;
 
    if (isPower(N, K)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
 
    return 0;
}

C

// C implementation to check if
// the number is power of K
#include <stdio.h>
#include <math.h>
 
// Function to check if
// the number is power of K
_Bool isPower(int N, int K)
{
     
    // Logarithm function to
    // calculate value
    int res1 = log(N) / log(K);
    double res2 = log(N) / log(K);
 
    // Compare to the result1
    // or result2 both are equal
    return (res1 == res2);
}
 
// Driver Code
int main()
{
    int N = 8;
    int K = 2;
 
    if (isPower(N, K))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}
 
// This code is contributed by vikas_g

Java

// Java implementation to check if
// the number is power of K
class GFG{
 
// Function to check if
// the number is power of K
static boolean isPower(int N, int K)
{
     
    // Logarithm function to
    // calculate value
    int res1 = (int)(Math.log(N) / Math.log(K));
    double res2 = Math.log(N) / Math.log(K);
 
    // Compare to the result1
    // or result2 both are equal
    return (res1 == res2);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 8;
    int K = 2;
 
    if (isPower(N, K))
    {
        System.out.println("Yes");
    }
    else
    {
        System.out.println("No");
    }
}
}
 
// This code is contributed by vikas_g

Python3

# Python3 implementation to check if a
# number is a power of the other number
from math import log
 
# Function to check if
# the number is power of K
def isPower(n, k):
     
    # Logarithm function to
    # calculate value
    res1 = int(log(n) / log(k))
    res2 = log(n) / log(k)
     
    # Compare to the result1
    # or result2 both are equal
    return(res1 == res2)
 
# Driver code
if __name__=="__main__":
     
    n = 8
    k = 2
     
    if (isPower(n, k)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by dipesh99kumar

C#

// C# implementation to check if
// the number is power of K
using System;
 
// Function to count the
// number of digits in a number
class GFG{
     
static bool isPower(int N, int K)
{
     
    // Logarithm function to
    // calculate value
    int res1 = (int)(Math.Log(N) / Math.Log(K));
    double res2 = Math.Log(N) / Math.Log(K);
 
    // Compare to the result1
    // or result2 both are equal
    return (res1 == res2);
}
 
// Driver Code
public static void Main()
{
    int N = 8;
    int K = 2;
 
    if (isPower(N, K))
    {
        Console.Write("Yes");
    }
    else
    {
        Console.Write("No");
    }
}
}
 
// This code is contributed by vikas_g

Javascript

<script>
//Javascript Implementation
// to check if
// the number is power of K
 
// Function to check if
// the number is power of K
function isPower(N, K)
{
    // logarithm function to
    // calculate value
    var res1 = Math.floor(Math.log(N) / Math.log(K));
    var res2 = Math.log(N) / Math.log(K);
 
    // compare to the result1
    // or result2 both are equal
    return (res1 == res2);
}
 
// Driver Code
var N = 8;
var K = 2;
 
if (isPower(N, K)) {
document.write("Yes");
}
else {
document.write("No");
}
// This code is contributed by shubhamsingh10
</script>

Producción:

Yes

Para encontrar la potencia de K mayor que igual y menor que igual a N:

Dados dos números enteros N y K , la tarea es encontrar la potencia de K mayor que igual y menor que igual a N.

Ejemplos:

Entrada: N = 7, K = 2
Salida: 4 8

Entrada: N = 18, K = 3
Salida: 9 27

Enfoque: La idea es encontrar el valor mínimo del valor logarítmico K del entero N dado, luego calcular la K ^-ésima potencia de este número para calcular la K ^-ésima potencia anterior y siguiente.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation to find the
// previous and next power of K
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to return the highest power
// of k less than or equal to n
int prevPowerofK(int n, int k)
{
    int p = (int)(log(n) / log(k));
    return (int)pow(k, p);
}
 
// Function to return the smallest power
// of k greater than or equal to n
int nextPowerOfK(int n, int k)
{
    return prevPowerofK(n, k) * k;
}
 
// Driver Code
int main()
{
    int N = 7;
    int K = 2;
 
    cout << prevPowerofK(N, K) << " ";
 
    cout << nextPowerOfK(N, K) << endl;
    return 0;
}

C

// C implementation to find the
// previous and next power of K
#include <stdio.h>
#include <math.h>
 
// Function to return the highest power
// of k less than or equal to n
int prevPowerofK(int n, int k)
{
    int p = (int)(log(n) / log(k));
    return (int)pow(k, p);
}
 
// Function to return the smallest power
// of k greater than or equal to n
int nextPowerOfK(int n, int k)
{
    return prevPowerofK(n, k) * k;
}
 
// Driver Code
int main()
{
    int N = 7;
    int K = 2;
 
    printf("%d ", prevPowerofK(N, K));
    printf("%d\n", nextPowerOfK(N, K));
     
    return 0;
}
 
// This code is contributed by vikas_g

Java

// Java implementation to find the
// previous and next power of K
class GFG{
 
// Function to return the highest power
// of k less than or equal to n
static int prevPowerofK(int n, int k)
{
    int p = (int)(Math.log(n) / Math.log(k));
    return (int)Math.pow(k, p);
}
 
// Function to return the smallest power
// of k greater than or equal to n
static int nextPowerOfK(int n, int k)
{
    return prevPowerofK(n, k) * k;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 7;
    int K = 2;
     
    System.out.print(prevPowerofK(N, K) + " ");
    System.out.println(nextPowerOfK(N, K));
}
}
 
// This code is contributed by vikas_g

Python3

# Python3 implementation to find the
# previous and next power of K
from math import log
 
# Function to return the highest power
# of k less than or equal to n
def prevPowerofK(n, k):
     
    p = (int)(log(n) / log(k));
    return pow(k, p);
 
# Function to return the smallest power
# of k greater than or equal to n
def nextPowerOfK(n, k):
     
    return prevPowerofK(n, k) * k;
 
# Driver Code
if __name__=="__main__":
     
    N = 7
    K = 2
     
    print(prevPowerofK(N, K), end = " ")
    print(nextPowerOfK(N, K))
 
# This code is contributed by dipesh99kumar

C#

// C# implementation to find the
// previous and next power of K
using System;
 
// Function to count the
// number of digits in a number
class GFG{
     
// Function to return the highest power
// of k less than or equal to n
static int prevPowerofK(int n, int k)
{
    int p = (int)(Math.Log(n) / Math.Log(k));
    return (int)Math.Pow(k, p);
}
 
// Function to return the smallest power
// of k greater than or equal to n
static int nextPowerOfK(int n, int k)
{
    return prevPowerofK(n, k) * k;
 
}
 
// Driver Code
public static void Main()
{
    int N = 7;
    int K = 2;
     
    Console.Write(prevPowerofK(N, K) + " ");
    Console.Write(nextPowerOfK(N, K));
}
}
 
// This code is contributed by vikas_g

Javascript

<script>
 
// Javascript implementation to find the
// previous and next power of K
 
// Function to return the highest power
// of k less than or equal to n
function prevPowerofK(n, k)
{
    let p = parseInt(Math.log(n) /
                     Math.log(k), 10);
    return Math.pow(k, p);
}
 
// Function to return the smallest power
// of k greater than or equal to n
function nextPowerOfK(n, k)
{
    return prevPowerofK(n, k) * k;
}
 
// Driver code
let N = 7;
let K = 2;
  
document.write(prevPowerofK(N, K) + " ");
document.write(nextPowerOfK(N, K));
 
// This code is contributed by rameshtravel07
 
</script>

Producción:

4 8

Para encontrar la posición del bit establecido más a la derecha:

Dado un número entero N , la tarea es encontrar la posición del bit establecido más a la derecha.

Ejemplos:

Entrada: N = 7
Salida: 1

Entrada: N = 8
Salida: 4

Acercarse:

Tome el complemento a dos del no dado ya que todos los bits se invierten excepto el primer ‘1’ de derecha a izquierda (0111)
Haga un bit-wise & con el original no, esto devolverá no con el requerido solo (0100)
Toma el log2 del no, obtendrás (posición – 1) (2)

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation to find the
// rightmost set bit
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the rightmost
// bit set of the integer N
unsigned int getFirstSetBitPos(int n)
{
    return log2(n & -n) + 1;
}
 
// Driver Code
int main()
{
    int N = 8;
 
    cout << getFirstSetBitPos(N);
    return 0;
}

C

// C implementation to find the
// rightmost set bit
#include <stdio.h>
#include <math.h>
 
// Function to find the rightmost
// bit set of the integer N
unsigned int getFirstSetBitPos(int n)
{
    return log2(n & -n) + 1;
}
 
// Driver Code
int main()
{
    int N = 8;
 
    printf("%d", getFirstSetBitPos(N));
    return 0;
}
 
// This code is contributed by vikas_g

Java

// Java implementation to find the
// rightmost set bit
class GFG{
 
// Function to find the rightmost
// bit set of the integer N
static int getFirstSetBitPos(int n)
{
    return (int)(Math.log(n & -n) /
                 Math.log(2)) + 1;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 8;
 
    System.out.println(getFirstSetBitPos(N));
}
}
 
// This code is contributed by vikas_g

Python3

# Python3 implementation to find the
# rightmost set bit
import math
 
# Function to find the rightmost
# bit set of the integer N
def getFirstSetBitPos(n):
 
    return math.log2(n & -n) + 1;
 
# Driver Code
if __name__=="__main__":
     
    N = 8
 
    print(int(getFirstSetBitPos(N)))
 
# This code is contributed by dipesh99kumar

C#

// C# implementation to find the
// rightmost set bit
using System;
 
class GFG{
 
// Function to find the rightmost
// bit set of the integer N
static int getFirstSetBitPos(int n)
{
    return (int)(Math.Log(n & -n) /
                 Math.Log(2)) + 1;
}
 
// Driver Code
public static void Main()
{
    int N = 8;
 
    Console.Write(getFirstSetBitPos(N));
}
}
 
// This code is contributed by vikas_g

Javascript

<script>
    // Javascript implementation to find the rightmost set bit
     
    // Function to find the rightmost
    // bit set of the integer N
    function getFirstSetBitPos(n)
    {
        return parseInt(Math.log(n & -n) / Math.log(2), 10) + 1;
    }
     
    let N = 8;
  
    document.write(getFirstSetBitPos(N));
     
    // This code is contributed by mukesh07.
 
</script>

Producción:

Publicación traducida automáticamente

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

Comprobando si un número es una potencia de dos o no:

C++

C

Java

Python3

C#

Javascript

K-ésima raíz de un número

C++

Java

Python3

C#

Javascript

Contar dígitos en un número:

C++

C

Java

Python3

C#

Javascript

Comprueba si N es una potencia de K o no:

C++

C

Java

Python3

C#

Javascript

Para encontrar la potencia de K mayor que igual y menor que igual a N:

C++

C

Java

Python3

C#

Javascript

Para encontrar la posición del bit establecido más a la derecha:

C++

C

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta