Given a positive integer N, the task is to count the number of different bases in which, when N is represented, the most significant bit of N is a found to be a set bit.
Examples:
Input: N = 6
Output: 4
Explanation: The number 6 can be represented in 5 different bases, i.e. base 2, base 3, base 4, base 5, base 6.
- (6)10 in base 2: (110)2
- (6)10 in base 3: (20)3
- (6)10 in base 4: (12)4
- (6)10 in base 5: (11)5
- (6)10 in base 6: (10)6
The base representation for (6)10 in base 2, base 4, base 5, base 6 starts with 1. Hence, the required count of bases is 4.
Input: N = 5
Output: 4
Approach: The given problem can be solved by finding the MSB of the given number N for every possible base and count those bases that have MSB as 1. Follow the steps below to solve the problem:
- Initialize a variable, say count as 0, to store the required result.
- Iterate over the range [2, N] using a variable, say B, and perform the following steps:
- Store the highest power of base B required to represent number N in a variable P. This can be easily achieved by finding the value of (log N to the base B) i.e., logB(N) truncated to the nearest integer.
- To find the value of logB(N) use the log property: logB(N) = log(N)/log(B)
- Store the most significant digit of N by dividing N by (B)P. If it is equal to 1, then increment the value of the count by 1.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
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 bitint 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 Codeint main(){ int N = 6; cout << countOfBase(N); return 0;} |
Java
// Java program for the above approachimport 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 approachusing System;using System.Collections.Generic;class GFG{// Function to count bases// having MSB of N as a set bitstatic 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 Codepublic 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 approachimport math# Function to count bases# having MSB of N as a set bitdef 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 CodeN = 6print(countOfBase(N)) |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
