Cuente las bases que contienen un bit establecido como el bit más significativo en la representación de N

Dado un entero positivo N , la tarea es contar el número de bases diferentes en las que, cuando se representa N , se encuentra que el bit más significativo de N es un bit establecido.

Ejemplos:

Entrada: N = 6
Salida: 4
Explicación: El número 6 se puede representar en 5 bases diferentes, es decir, base 2, base 3, base 4, base 5, base 6.

1. (6) ₁₀  en base 2: (110) ₂
2. (6) ₁₀  en base 3: (20) ₃
3. (6) ₁₀  en base 4: (12) ₄
4. (6) ₁₀  en base 5: (11) ₅
5. (6) ₁₀  en base 6: (10) ₆

La representación base para (6) ₁₀ en base 2, base 4, base 5, base 6 comienza con 1. Por lo tanto, el conteo requerido de bases es 4.

Entrada: N = 5
Salida: 4

Enfoque: El problema dado se puede resolver encontrando el MSB del número N dado para cada base posible y contando esas bases que tienen MSB como 1 . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos contar como 0 , para almacenar el resultado requerido.
• Itere sobre el rango [2, N] usando una variable, digamos B , y realice los siguientes pasos:
  • Almacene la potencia más alta de la base B requerida para representar el número N en una variable P . Esto se puede lograr fácilmente encontrando el valor de ( log N en base B ), es decir, log _B (N) truncado al entero más cercano.
  • Para encontrar el valor de log _B (N) use la propiedad de registro: log _B (N) = log (N)/log (B)
  • Almacene el dígito más significativo de N dividiendo N por (B) ^P . Si es igual a 1 , incremente el valor de la cuenta en 1.
• Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count bases
// having MSB of N as a set bit
int countOfBase(int N)
{
    // Store the required count
    int count = 0;
 
    // Iterate over the range [2, N]
    for (int i = 2; i <= N; ++i) {
 
        int highestPower
            = (int)(log(N) / log(i));
 
        // Store the MSB of N
        int firstDigit = N / (int)pow(
                                 i, highestPower);
 
        // If MSB is 1, then increment
        // the count by 1
        if (firstDigit == 1) {
            ++count;
        }
    }
 
    // Return the count
    return count;
}
 
// Driver Code
int main()
{
    int N = 6;
    cout << countOfBase(N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG {
     
 public static int countOfBase(int N)
{
    
    // Store the required count
    int count = 0;
 
    // Iterate over the range [2, N]
    for (int i = 2; i <= N; ++i) {
 
        int highestPower
            = (int)(Math.log(N) /Math.log(i));
 
        // Store the MSB of N
        int firstDigit = N / (int)Math.pow(
                                 i, highestPower);
 
        // If MSB is 1, then increment
        // the count by 1
        if (firstDigit == 1) {
            ++count;
        }
    }
 
    // Return the count
    return count;
}
 
  // DRIVER CODE
    public static void main (String[] args)
    {
       int N = 6;
 
        System.out.println(countOfBase(N));
    }
}
 
 // This code is contributed by Potta Lokesh

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count bases
// having MSB of N as a set bit
static int countOfBase(int N)
{
     
    // Store the required count
    int count = 0;
     
    // Iterate over the range [2, N]
    for(int i = 2; i <= N; ++i)
    {
     
        int highestPower = (int)(Math.Log(N) /
                                 Math.Log(i));
         
        // Store the MSB of N
        int firstDigit = N / (int)Math.Pow(
                                 i, highestPower);
         
        // If MSB is 1, then increment
        // the count by 1
        if (firstDigit == 1)
        {
            ++count;
        }
    }
     
    // Return the count
    return count;
}
 
// Driver Code
public static void Main()
{
    int N = 6;
     
    Console.Write(countOfBase(N));
}
}
 
// This code is contributed by ipg2016107

<script>
        // JavaScript implementation of the approach
        function countOfBase(N)
        {
         
            // Store the required count
            let count = 0;
 
            // Iterate over the range [2, N]
            for (let i = 2; i <= N; ++i) {
 
                let highestPower
                    = parseInt(Math.log(N) / Math.log(i));
 
                // Store the MSB of N
                let firstDigit = parseInt(N / Math.pow(
                    i, highestPower));
 
                // If MSB is 1, then increment
                // the count by 1
                if (firstDigit == 1) {
                    ++count;
                }
            }
 
            // Return the count
            return count;
        }
         
        // Driver code
        let N = 6;
        document.write(countOfBase(N))
 
// This code is contributed by Potta Lokesh
 
 
    </script>

# Python 3 program for the above approach
import math
 
# Function to count bases
# having MSB of N as a set bit
def countOfBase(N) :
     
    # Store the required count
    count = 0
 
    # Iterate over the range [2, N]
    for i in range(2, N+1):
 
        highestPower = int(math.log(N) / math.log(i))
 
        # Store the MSB of N
        firstDigit = int(N / int(math.pow(i, highestPower)))
 
        # If MSB is 1, then increment
        # the count by 1
        if (firstDigit == 1) :
            count += 1
         
     
 
    # Return the count
    return count
 
 
# Driver Code
 
N = 6
print(countOfBase(N))

4

Complejidad temporal: O(N)
Espacio auxiliar: O(1)