Given a positive integer N, the task is to find the number that can be obtained by flipping consecutive set bits starting from the LSB in the binary representation of N.
Examples:
Input: N = 39
Output: 32
Explanation:
Binary representation of (39)10 = (100111)2
After flipping all consecutive set bits starting from the LSB, the number obtained is (100000)
Binary representation of (32)10 is (100000)2
Therefore, the number obtained is 32.Input: N = 4
Output: 4
Explanation:
Binary representation of (4)10 = (100)2
Since the LSB is not set, the number remains unchanged.
Naive Approach: The simplest approach is to find the number of consecutive set bits starting from the LSB by performing Logical AND( & ) of N with 1 until N & 1 is not 0 and keep a count of the number of set bits. Then, simply left shift N by the count of set bits. Print the number obtained as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number after// converting 1s from end to 0sint findNumber(int N){ // Count of 1s int count = 0; // AND operation of N and 1 while ((N & 1) == 1) { N = N >> 1; count++; } // Left shift N by count return N << count;}// Driver Codeint main(){ int N = 39; // Function Call cout << findNumber(N); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to find the number after// converting 1s from end to 0sstatic int findNumber(int N){ // Count of 1s int count = 0; // AND operation of N and 1 while ((N & 1) == 1) { N = N >> 1; count++; } // Left shift N by count return N << count;}// Driver Codepublic static void main (String[] args){ int N = 39; // Function Call System.out.println(findNumber(N));}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the number after# converting 1s from end to 0sdef findNumber(N): # Count of 1s count = 0 # AND operation of N and 1 while ((N & 1) == 1): N = N >> 1 count += 1 # Left shift N by count return N << count# Driver Codeif __name__ == "__main__": N = 39 # Function Call print(findNumber(N))# This code is contributed by AnkThon |
C#
// C# program to implement// the above approach using System; class GFG{ // Function to find the number after// converting 1s from end to 0sstatic int findNumber(int N){ // Count of 1s int count = 0; // AND operation of N and 1 while ((N & 1) == 1) { N = N >> 1; count++; } // Left shift N by count return N << count;}// Driver Codepublic static void Main(){ int N = 39; // Function Call Console.WriteLine(findNumber(N));}}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program for the above approach// Function to find the number after// converting 1s from end to 0sfunction findNumber(N){ // Count of 1s let count = 0; // AND operation of N and 1 while ((N & 1) == 1) { N = N >> 1; count++; } // Left shift N by count return N << count;}// Driver Code let N = 39; // Function Call document.write(findNumber(N)); </script> |
32
Time Complexity: O(log N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, find the Logical AND ( & ) of N and (N + 1). The key observation is that adding 1 to a number makes every continuous set bit from the LSB to become 0. Therefore, N & (N + 1) gives the required number.
Illustration:
N = 39, therefore (N+1)=40 ? N = 39 = (100111) ? N+1 = 40 = (101000) Performing Logical AND(&) operation: 1 0 0 1 1 1 & 1 0 1 0 0 0 ---------------- 1 0 0 0 0 0 ? 32 ---------------- Will this always work? Add 1 to N: 1 0 0 1 1 1 + 1 ------------- 1 0 1 0 0 0 -------------- It can be clearly seen that the continuous set bits from the LSB becomes unset.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number after// converting 1s from end to 0sint findNumber(int N){ // Return the logical AND // of N and (N + 1) return N & (N + 1);}// Driver Codeint main(){ int N = 39; // Function Call cout << findNumber(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the number after// converting 1s from end to 0sstatic int findNumber(int N){ // Return the logical AND // of N and (N + 1) return N & (N + 1);}// Driver Codepublic static void main(String[] args){ int N = 39; // Function Call System.out.print(findNumber(N));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find the number after# converting 1s from end to 0sdef findNumber(N): # Return the logical AND # of N and (N + 1) return N & (N + 1)# Driver Codeif __name__ == '__main__': N = 39 # Function Call print(findNumber(N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the number after// converting 1s from end to 0sstatic int findNumber(int N){ // Return the logical AND // of N and (N + 1) return N & (N + 1);}// Driver Codepublic static void Main(String[] args){ int N = 39; // Function Call Console.Write(findNumber(N));}} // This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program of the above approach// Function to find the number after// converting 1s from end to 0sfunction findNumber(N){ // Return the logical AND // of N and (N + 1) return N & (N + 1);} // Driver Code let N = 39; // Function Call document.write(findNumber(N)); // This code is contributed by target_2.</script> |
32
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
