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.
- (6) 10 en base 2: (110) 2
- (6) 10 en base 3: (20) 3
- (6) 10 en base 4: (12) 4
- (6) 10 en base 5: (11) 5
- (6) 10 en base 6: (10) 6
La representación base para (6) 10 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++
// 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
// 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#
// 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
Javascript
<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>
Python3
# 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)