Toggle Bits From MSB

Easy

0/40

0 upvote

Problem statement

You are given a non-negative integer 'n'. Your task is to toggle all the bits of this number from the Most Significant Bit (MSB) downwards, including the MSB itself.

The Most Significant Bit (MSB) is the leftmost '1' in the binary representation of the number. For example, if the number is 10 (binary 1010), its MSB is the first '1'. Toggling from the MSB downwards would change 1010 to 0101 (which is 5 in decimal).

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

A single line containing an integer 'n'.

Output Format:

Print a single integer representing the result after toggling the bits.

Note:

Toggling a bit means changing a 0 to a 1, and a 1 to a 0.
The input 'n' is a non-negative integer.
For the input n=0, its binary representation is 0. The MSB is considered to be at the 0th position. Toggling it results in 1.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

The binary representation of 10 is `1010`.
The Most Significant Bit (MSB) is the leftmost '1'.
Toggling all bits from the MSB downwards means toggling `1010`.
`1` becomes `0`, `0` becomes `1`, `1` becomes `0`, `0` becomes `1`.
The result is `0101`, which is 5 in decimal.

Sample Input 2:

Sample Output 2:

Explanation for Sample 2:

The binary representation of 5 is `101`.
Toggling all bits from the MSB downwards means toggling `101`.
The result is `010`, which is 2 in decimal.

Expected Time Complexity:

The expected time complexity is O(log n).

Constraints:

0 <= n <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Toggle Bits From MSB

Time Complexity

The expected time complexity is O(log n)

Space Complexity

(100% EXP penalty)

Toggle Bits From MSB

Console