Given a binary number as a string str of length L. The task is to find the minimum number of operations needed so that the number becomes 2L-1, that is a string consisting of only 1’s of the length L.
In each operation, the number N can be replaced by N xor (N + 1).
Examples:
Input: str = “10010111”
Output: 5
N = 10010111, N + 1 = 10011000, so N xor (N + 1) = 00001111
N = 00001111, N + 1 = 00010000, so N xor (N + 1) = 00011111
N = 00011111, N + 1 = 00100000, so N xor (N + 1) = 00111111
N = 00111111, N + 1 = 01000000, so N xor (N + 1) = 01111111
N = 01111111, N + 1 = 10000000, so N xor (N + 1) = 11111111Input: str = “101000100101011101”
Output: 17
Approach: After performing the given operation, it can be observed that in order to get the required number, in the end, the number of operations will be:
Number of Operations = length of the string (after removing leading 0s) – count of consecutive 1’s form the end (starting from the least significant bit)
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the number// of operations requiredint changeToOnes(string str){ // ctr will store the number of // consecutive ones at the end // of the given binary string int i, l, ctr = 0; l = str.length(); // Loop to find number of 1s // at the end of the string for (i = l - 1; i >= 0; i--) { // If the current character is 1 if (str[i] == '1') ctr++; // If we encounter the first 0 // from the LSB position then // we'll break the loop else break; } // Number of operations // required is (l - ctr) return l - ctr;}// Function to remove leading// zeroes from the stringstring removeZeroesFromFront(string str){ string s; int i = 0; // Loop until s[i] becomes // not equal to 1 while (i < str.length() && str[i] == '0') i++; // If we reach the end of // the string, it means that // string contains only 0's if (i == str.length()) s = "0"; // Return the string without // leading zeros else s = str.substr(i, str.length() - i); return s;}// Driver codeint main(){ string str = "10010111"; // Removing the leading zeroes str = removeZeroesFromFront(str); cout << changeToOnes(str); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to return the number// of operations requiredstatic int changeToOnes(String str){ // ctr will store the number of // consecutive ones at the end // of the given binary string int i, l, ctr = 0; l = str.length(); // Loop to find number of 1s // at the end of the string for (i = l - 1; i >= 0; i--) { // If the current character is 1 if (str.charAt(i) == '1') ctr++; // If we encounter the first 0 // from the LSB position then // we'll break the loop else break; } // Number of operations // required is (l - ctr) return l - ctr;}// Function to remove leading// zeroes from the stringstatic String removeZeroesFromFront(String str){ String s; int i = 0; // Loop until s[i] becomes // not equal to 1 while (i < str.length() && str.charAt(i) == '0') i++; // If we reach the end of // the string, it means that // string contains only 0's if (i == str.length()) s = "0"; // Return the string without // leading zeros else s = str.substring(i, str.length() - i); return s;}// Driver codepublic static void main(String[] args) { String str = "10010111"; // Removing the leading zeroes str = removeZeroesFromFront(str); System.out.println(changeToOnes(str));}} // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to return the number # of operations required def changeToOnes(string) : # ctr will store the number of # consecutive ones at the end # of the given binary string ctr = 0; l = len(string); # Loop to find number of 1s # at the end of the string for i in range(l - 1, -1, -1) : # If the current character is 1 if (string[i] == '1') : ctr += 1; # If we encounter the first 0 # from the LSB position then # we'll break the loop else : break; # Number of operations # required is (l - ctr) return l - ctr; # Function to remove leading # zeroes from the string def removeZeroesFromFront(string) : s = ""; i = 0; # Loop until s[i] becomes # not equal to 1 while (i < len(string) and string[i] == '0') : i += 1; # If we reach the end of # the string, it means that # string contains only 0's if (i == len(string)) : s = "0"; # Return the string without # leading zeros else : s = string[i: len(string) - i]; return s; # Driver code if __name__ == "__main__" : string = "10010111"; # Removing the leading zeroes string = removeZeroesFromFront(string); print(changeToOnes(string)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG {// Function to return the number// of operations requiredstatic int changeToOnes(String str){ // ctr will store the number of // consecutive ones at the end // of the given binary string int i, l, ctr = 0; l = str.Length; // Loop to find number of 1s // at the end of the string for (i = l - 1; i >= 0; i--) { // If the current character is 1 if (str[i] == '1') ctr++; // If we encounter the first 0 // from the LSB position then // we'll break the loop else break; } // Number of operations // required is (l - ctr) return l - ctr;}// Function to remove leading// zeroes from the stringstatic String removeZeroesFromFront(String str){ String s; int i = 0; // Loop until s[i] becomes // not equal to 1 while (i < str.Length && str[i] == '0') i++; // If we reach the end of // the string, it means that // string contains only 0's if (i == str.Length) s = "0"; // Return the string without // leading zeros else s = str.Substring(i, str.Length - i); return s;}// Driver codepublic static void Main(String[] args) { String str = "10010111"; // Removing the leading zeroes str = removeZeroesFromFront(str); Console.WriteLine(changeToOnes(str));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach// Function to return the number// of operations requiredfunction changeToOnes(str){ // ctr will store the number of // consecutive ones at the end // of the given binary string var i, l, ctr = 0; l = str.length; // Loop to find number of 1s // at the end of the string for (i = l - 1; i >= 0; i--) { // If the current character is 1 if (str[i] == '1') ctr++; // If we encounter the first 0 // from the LSB position then // we'll break the loop else break; } // Number of operations // required is (l - ctr) return l - ctr;}// Function to remove leading// zeroes from the stringfunction removeZeroesFromFront(str){ var s; var i = 0; // Loop until s[i] becomes // not equal to 1 while (i < str.length && str[i] == '0') i++; // If we reach the end of // the string, it means that // string contains only 0's if (i == str.length) s = "0"; // Return the string without // leading zeros else s = str.substring(i, str.length - i); return s;}// Driver codevar str = "10010111";// Removing the leading zeroesstr = removeZeroesFromFront(str);document.write( changeToOnes(str));</script> |
Output
5
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: 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!
