Given a binary number, the task is to remove exactly one bit from it such that, after it’s removal, the resultant binary number is greatest from all the options.
Examples:
Input: 110
Output: 11
As 110 = 6 in decimal,
the option is to remove either 0 or 1.
So the possible combinations are 10, 11
The max number is 11 = 3 in decimal.
Input:1001
Output: 101
Approach:
- Traverse the binary number from left to right.
- Find the least redundant 0 bit, as this bit will have the least effect on the resultant binary number.
- Skip this bit, or remove it.
- The rest of the bits give the maximum value binary number.
Below is the implementation of the above approach:
Program:
C++
// C++ program to find next maximum binary number// with one bit removed#include <bits/stdc++.h>using namespace std;// Function to find the maximum binary numberint printMaxAfterRemoval(string s){ bool flag = false; int n = s.length(); // Traverse the binary number for (int i = 0; i < n; i++) { // Try finding a 0 and skip it if (s[i] == '0' && flag == false) { flag = true; continue; } else cout << s[i]; }}// Driver codeint main(){ // Get the binary number string s = "1001"; // Find the maximum binary number printMaxAfterRemoval(s);} |
Java
// Java program to find next maximum binary number// with one bit removedimport java.io.*;class GFG { // Function to find the maximum binary numberstatic int printMaxAfterRemoval(String s){ boolean flag = false; int n = s.length(); // Traverse the binary number for (int i = 0; i < n; i++) { // Try finding a 0 and skip it if (s.charAt(i) == '0' && flag == false) { flag = true; continue; } else System.out.print( s.charAt(i)); } return 0;}// Driver code public static void main (String[] args) { // Get the binary number String s = "1001"; // Find the maximum binary number printMaxAfterRemoval(s); }}// This code is contributed by anuj_67.. |
Python3
# Python3 program to find next maximum # binary number with one bit removed # Function to find the maximum# binary number def printMaxAfterRemoval(s): flag = False n = len(s) # Traverse the binary number for i in range(0, n): # Try finding a 0 and skip it if s[i] == '0' and flag == False: flag = True continue else: print(s[i], end = "") # Driver code if __name__ == "__main__": # Get the binary number s = "1001" # Find the maximum binary number printMaxAfterRemoval(s) # This code is contributed # by Rituraj Jain |
C#
// C# program to find next maximum // binary number with one bit removedusing System;class GFG {// Function to find the maximum// binary numberstatic int printMaxAfterRemoval(String s){ bool flag = false; int n = s.Length; // Traverse the binary number for (int i = 0; i < n; i++) { // Try finding a 0 and skip it if (s[i] == '0' && flag == false) { flag = true; continue; } else Console.Write(s[i]); } return 0;}// Driver Codestatic void Main(){ // Get the binary number String s = "1001"; // Find the maximum binary number printMaxAfterRemoval(s);}}// This code is contributed by Ryuga. |
PHP
<?php// PHP program to find next maximum // binary number with one bit removed// Function to find the maximum// binary numberfunction printMaxAfterRemoval($s){ $flag = false; $n = strlen($s); // Traverse the binary number for ($i = 0; $i < $n; $i++) { // Try finding a 0 and skip it if ($s[$i] == '0' && $flag == false) { $flag = true; continue; } else echo $s[$i]; }}// Driver code// Get the binary number$s = "1001";// Find the maximum binary numberprintMaxAfterRemoval($s);// This code is contributed // by Akanksha Rai?> |
Javascript
<script> // Javascript program to find next maximum // binary number with one bit removed // Function to find the maximum // binary number function printMaxAfterRemoval(s) { let flag = false; let n = s.length; // Traverse the binary number for (let i = 0; i < n; i++) { // Try finding a 0 and skip it if (s[i] == '0' && flag == false) { flag = true; continue; } else document.write(s[i]); } return 0; } // Get the binary number let s = "1001"; // Find the maximum binary number printMaxAfterRemoval(s); </script> |
Output:
101
Time Complexity: O(n)
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!
… [Trackback]
[…] Read More Information here on that Topic: geeksforgeeks.org/remove-one-bit-from-a-binary-number-to-get-maximum-value/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/remove-one-bit-from-a-binary-number-to-get-maximum-value/ […]