Find most significant bit of a number X in base Y

0 0 3 minutes read

Given two positive integers X and Y, the task is to find the MSB of X, in the given base Y.
Examples:

Input: X = 55, Y = 3
Output: 2
Explanation:
55 is 2001 in base 3 with first digit as 2.
Input: X = 123, Y = 10
Output: 1
Explanation:
123 is 123 in base 10 with first digit 1.

Approach: Let the task to find 1st digit of X = 1234 in base Y = 10, So to get First digit = 1:

Divide 1234 by 1000
= X / 10³
= X / 10^{Number of Digits in X – 1}
= X / 10^{log(X) / log(10)} (which is for base 10)

For any other base, we can replace 10 with Y. Therefore, we can calculate the first digit of a number X in base Y by using the formula:

X / Y^{(log(X)/log(Y))}

Below is the implementation of the above approach:

C++

// C++ Program to find the
// first digit of X in base Y
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the first
// digit of X in base Y
void first_digit(int x, int y)
{
    // calculating number of digits of
    // x in base y
    int length = log(x) / log(y) + 1;
 
    // finding first digit of x in base y
    int first_digit = x / pow(y, length - 1);
 
    cout << first_digit;
}
 
// Driver code
int main()
{
    int X = 55, Y = 3;
 
    first_digit(X, Y);
 
    return 0;
}

Java

// Java Program to find the
// first digit of X in base Y
import java.util.*;
class GFG{
 
// Function to find the first
// digit of X in base Y
static void first_digit(int x, int y)
{
    // calculating number of digits of
    // x in base y
    int length = (int)(Math.log(x) / 
                       Math.log(y) + 1);
 
    // finding first digit of x in base y
    int first_digit = (int)(x / Math.pow(y, 
                                length - 1));
 
    System.out.println(first_digit);
}
 
// Driver code
public static void main(String args[])
{
    int X = 55, Y = 3;
 
    first_digit(X, Y);
}
}
 
// This code is contributed by AbhiThakur

Python3

# Python3 program to find the 
# first digit of X in base Y 
import math
 
# Function to find the first 
# digit of X in base Y 
def first_digit(x, y):
     
    # Calculating number of digits of 
    # x in base y 
    length = int (math.log(x) /
                  math.log(y) + 1) 
     
    # Finding first digit of x in base y
    first_digit = x / math.pow(y, length - 1)
 
    print(int(first_digit))
     
# Driver code 
X = 55
Y = 3
 
first_digit(X, Y)
 
# This code is contributed by ishayadav181

C#

// C# Program to find the
// first digit of X in base Y
using System;
class GFG{
 
// Function to find the first
// digit of X in base Y
static void first_digit(int x, int y)
{
    // calculating number of digits of
    // x in base y
    int length = (int)(Math.Log(x) / 
                       Math.Log(y) + 1);
 
    // finding first digit of x in base y
    int first_digit = (int)(x / Math.Pow(y, 
                                length - 1));
 
    Console.Write(first_digit);
}
 
// Driver code
public static void Main()
{
    int X = 55, Y = 3;
 
    first_digit(X, Y);
}
}
 
// This code is contributed by Akanksha_Rai

Javascript

<script>
 
// Javascript Program to find the
// first digit of X in base Y
 
// Function to find the first
// digit of X in base Y
function first_digit(x, y)
{
    // calculating number of digits of
    // x in base y
    var length = parseInt(Math.log(x) / Math.log(y)) + 1;
 
    // finding first digit of x in base y
    var first_digit = parseInt(x / Math.pow(y, length - 1));
 
    document.write( first_digit);
}
 
// Driver code
var X = 55, Y = 3;
first_digit(X, Y);
 
</script>

Output:

Time Complexity: O(1)

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 zambiatek!