BITMEDU7 - Editorial

Problem Link - Finding least significant, most significant bit

Problem Statement

  • Write a program to input an integer N.

  • Print the position of the most significant bit, and print the least significant bit.

Approach

The code idea is to determine two key properties of the input integer N: the position of the most significant bit (MSB) and the value of the least significant bit (LSB).

  1. Least Significant Bit (LSB): This is obtained by performing a bitwise AND operation between N and 1. If N is odd, the LSB will be 1, and if it is even, the LSB will be 0.

  2. Most Significant Bit (MSB): The position of the MSB is found by repeatedly dividing N by 2 until N becomes 0, while keeping track of the number of divisions. The position of the MSB is then the count of divisions minus one since the counting starts from 1.

Time Complexity

The time complexity of the algorithm is O(log N), as it involves repeatedly dividing N by 2.

Space Complexity

The space complexity of the algorithm is O(1), since it uses a constant amount of space for variables.