Given a binary input that represents binary representation of positive number n, find binary representation of smallest number greater than n with same number of 1’s and 0’s as in binary representation of n. If no such number can be formed, print “no greater number”.
The binary input may be and may not fit even in unsigned long long int.
Examples:
Input : 10010
Output : 10100
Here n = (18)10 = (10010)2
next greater = (20)10 = (10100)2
Binary representation of 20 contains same number of
1's and 0's as in 18.
Input : 111000011100111110
Output : 111000011101001111
This problem simply boils down to finding next permutation of a given string. We can find the next_permutation() of the input binary number.
Below is an algorithm to find next permutation in binary string.
- Traverse the binary string bstr from the right.
- While traversing find the first index i such that bstr[i] = ‘0’ and bstr[i+1] = ‘1’.
- Exchange character of at index ‘i’ and ‘i+1’.
- Since we need smallest next value, consider substring from index i+2 to end and move all 1’s in the substring in the end.
Below is the implementation of above steps.
C++
// C++ program to find next permutation in a// binary string.#include <bits/stdc++.h>using namespace std;// Function to find the next greater number// with same number of 1's and 0'sstring nextGreaterWithSameDigits(string bnum){ int l = bnum.size(); int i; for (int i=l-2; i>=1; i--) { // locate first 'i' from end such that // bnum[i]=='0' and bnum[i+1]=='1' // swap these value and break; if (bnum.at(i) == '0' && bnum.at(i+1) == '1') { char ch = bnum.at(i); bnum.at(i) = bnum.at(i+1); bnum.at(i+1) = ch; break; } } // if no swapping performed if (i == 0) "no greater number"; // Since we want the smallest next value, // shift all 1's at the end in the binary // substring starting from index 'i+2' int j = i+2, k = l-1; while (j < k) { if (bnum.at(j) == '1' && bnum.at(k) == '0') { char ch = bnum.at(j); bnum.at(j) = bnum.at(k); bnum.at(k) = ch; j++; k--; } // special case while swapping if '0' // occurs then break else if (bnum.at(i) == '0') break; else j++; } // required next greater number return bnum;}// Driver program to test aboveint main(){ string bnum = "10010"; cout << "Binary representation of next greater number = " << nextGreaterWithSameDigits(bnum); return 0;} |
Java
// Java program to find next permutation in a// binary string.class GFG {// Function to find the next greater number// with same number of 1's and 0'sstatic String nextGreaterWithSameDigits(char[] bnum){ int l = bnum.length; int i; for (i = l - 2; i >= 1; i--) { // locate first 'i' from end such that // bnum[i]=='0' and bnum[i+1]=='1' // swap these value and break; if (bnum[i] == '0' && bnum[i+1] == '1') { char ch = bnum[i]; bnum[i] = bnum[i+1]; bnum[i+1] = ch; break; } } // if no swapping performed if (i == 0) System.out.println("no greater number"); // Since we want the smallest next value, // shift all 1's at the end in the binary // substring starting from index 'i+2' int j = i + 2, k = l - 1; while (j < k) { if (bnum[j] == '1' && bnum[k] == '0') { char ch = bnum[j]; bnum[j] = bnum[k]; bnum[k] = ch; j++; k--; } // special case while swapping if '0' // occurs then break else if (bnum[i] == '0') break; else j++; } // required next greater number return String.valueOf(bnum);}// Driver program to test abovepublic static void main(String[] args){ char[] bnum = "10010".toCharArray(); System.out.println("Binary representation of next greater number = " + nextGreaterWithSameDigits(bnum));}}// This code contributed by Rajput-Ji |
Python3
# Python3 program to find next permutation in a# binary string.# Function to find the next greater number# with same number of 1's and 0'sdef nextGreaterWithSameDigits(bnum): l = len(bnum) bnum = list(bnum) for i in range(l - 2, 0, -1): # locate first 'i' from end such that # bnum[i]=='0' and bnum[i+1]=='1' # swap these value and break if (bnum[i] == '0' and bnum[i + 1] == '1'): ch = bnum[i] bnum[i] = bnum[i + 1] bnum[i + 1] = ch break # if no swapping performed if (i == 0): return "no greater number" # Since we want the smallest next value, # shift all 1's at the end in the binary # substring starting from index 'i+2' j = i + 2 k = l - 1 while (j < k): if (bnum[j] == '1' and bnum[k] == '0'): ch = bnum[j] bnum[j] = bnum[k] bnum[k] = ch j += 1 k -= 1 # special case while swapping if '0' # occurs then break else if (bnum[i] == '0'): break else: j += 1 # required next greater number return bnum# Driver codebnum = "10010"print("Binary representation of next greater number = ",*nextGreaterWithSameDigits(bnum),sep="")# This code is contributed by shubhamsingh10 |
C#
// C# program to find next permutation in a// binary string.using System;class GFG {// Function to find the next greater number// with same number of 1's and 0'sstatic String nextGreaterWithSameDigits(char[] bnum){ int l = bnum.Length; int i; for (i = l - 2; i >= 1; i--) { // locate first 'i' from end such that // bnum[i]=='0' and bnum[i+1]=='1' // swap these value and break; if (bnum[i] == '0' && bnum[i+1] == '1') { char ch = bnum[i]; bnum[i] = bnum[i+1]; bnum[i+1] = ch; break; } } // if no swapping performed if (i == 0) Console.WriteLine("no greater number"); // Since we want the smallest next value, // shift all 1's at the end in the binary // substring starting from index 'i+2' int j = i + 2, k = l - 1; while (j < k) { if (bnum[j] == '1' && bnum[k] == '0') { char ch = bnum[j]; bnum[j] = bnum[k]; bnum[k] = ch; j++; k--; } // special case while swapping if '0' // occurs then break else if (bnum[i] == '0') break; else j++; } // required next greater number return String.Join("",bnum);}// Driver codepublic static void Main(String[] args){ char[] bnum = "10010".ToCharArray(); Console.WriteLine("Binary representation of next greater number = " + nextGreaterWithSameDigits(bnum));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find next permutation// in a binary string.// Function to find the next greater number// with same number of 1's and 0'sfunction nextGreaterWithSameDigits(bnum){ let l = bnum.length; let i; for(i = l - 2; i >= 1; i--) { // Locate first 'i' from end such that // bnum[i]=='0' and bnum[i+1]=='1' // swap these value and break; if (bnum[i] == '0' && bnum[i + 1] == '1') { let ch = bnum[i]; bnum[i] = bnum[i+1]; bnum[i+1] = ch; break; } } // If no swapping performed if (i == 0) document.write("no greater number<br>"); // Since we want the smallest next value, // shift all 1's at the end in the binary // substring starting from index 'i+2' let j = i + 2, k = l - 1; while (j < k) { if (bnum[j] == '1' && bnum[k] == '0') { let ch = bnum[j]; bnum[j] = bnum[k]; bnum[k] = ch; j++; k--; } // Special case while swapping if '0' // occurs then break else if (bnum[i] == '0') break; else j++; } // Required next greater number return (bnum).join("");}// Driver codelet bnum = "10010".split("");document.write("Binary representation of next " + "greater number = " + nextGreaterWithSameDigits(bnum));// This code is contributed by rag2127</script> |
Output
Binary representation of next greater number = 10100
Time Complexity : O(n) where n is number of bits in input.
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Approach 2 :
Here’s the approach to find the next greater number with the same number of 1’s and 0’s in a binary string:
- Find the rightmost non-trailing one (RT1) in the string. Let its index be i.
- If there is no RT1, then the given binary string is already the largest possible binary string with the same number of 1’s and 0’s. Return “no greater number”.
- Find the rightmost zero to the right of i (let its index be j), and swap it with the RT1.
- Sort the substring to the right of j in ascending order.
- Return the resulting string.
Here’s the corrected C++ and Java code for this approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find the next greater number// with same number of 1's and 0'sstring nextGreaterWithSameDigits(string bnum){ int l = bnum.size(); int i = l - 1; // Find the rightmost non-trailing one while (i >= 0 && bnum[i] == '0') { i--; } if (i < 0) { return "no greater number"; } // Find the rightmost zero to the right of i int j = i - 1; while (j >= 0 && bnum[j] == '1') { j--; } if (j < 0) { return "no greater number"; } // Swap the RT1 with the rightmost zero to the right of i swap(bnum[i], bnum[j]); // Sort the substring to the right of j in ascending order sort(bnum.begin() + j + 1, bnum.end()); // Required next greater number return bnum;}// Driver program to test aboveint main(){ string bnum = "10010"; cout << "Binary representation of next greater number = " << nextGreaterWithSameDigits(bnum); return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to find the next greater number // with the same number of 1's and 0's public static String nextGreaterWithSameDigits(String bnum) { int l = bnum.length(); int i = l - 1; // Find the rightmost non-trailing one while (i >= 0 && bnum.charAt(i) == '0') { i--; } if (i < 0) { return "no greater number"; } // Find the rightmost zero to the right of i int j = i - 1; while (j >= 0 && bnum.charAt(j) == '1') { j--; } if (j < 0) { return "no greater number"; } // Swap the RT1 with the rightmost zero to the right of i char[] bnumArray = bnum.toCharArray(); char temp = bnumArray[i]; bnumArray[i] = bnumArray[j]; bnumArray[j] = temp; // Sort the substring to the right of j in ascending order Arrays.sort(bnumArray, j + 1, l); // Required next greater number return new String(bnumArray); } // Driver program to test above public static void main(String[] args) { String bnum = "10010"; System.out.println("Binary representation of next greater number = " + nextGreaterWithSameDigits(bnum)); }} |
Python
# Function to find the next greater number# with the same number of 1's and 0'sdef next_greater_with_same_digits(bnum): l = len(bnum) i = l - 1 # Find the rightmost non-trailing one while i >= 0 and bnum[i] == '0': i -= 1 if i < 0: return "no greater number" # Find the rightmost zero to the right of i j = i - 1 while j >= 0 and bnum[j] == '1': j -= 1 if j < 0: return "no greater number" # Swap the rightmost one with the rightmost zero to the right of i bnum_list = list(bnum) bnum_list[i], bnum_list[j] = bnum_list[j], bnum_list[i] bnum = ''.join(bnum_list) # Sort the substring to the right of j in ascending order bnum = bnum[:j + 1] + ''.join(sorted(bnum[j + 1:])) # Required next greater number return bnum# Driver program to test the functionif __name__ == "__main__": bnum = "10010" result = next_greater_with_same_digits(bnum) print("Binary representation of the next greater number =", result) |
C#
using System;namespace NextGreaterNumberWithSameDigits{ class GFG { // Function to find the next greater number // with same number of 1's and 0's static string NextGreaterWithSameDigits(string bnum) { int l = bnum.Length; int i = l - 1; // Find the rightmost non-trailing one while (i >= 0 && bnum[i] == '0') { i--; } if (i < 0) { return "no greater number"; } // Find the rightmost zero to the right of i int j = i - 1; while (j >= 0 && bnum[j] == '1') { j--; } if (j < 0) { return "no greater number"; } // Swap the RT1 with the rightmost zero to the right of i char[] bnumArray = bnum.ToCharArray(); char temp = bnumArray[i]; bnumArray[i] = bnumArray[j]; bnumArray[j] = temp; // Sort the substring to the right of j in ascending order Array.Sort(bnumArray, j + 1, l - j - 1); // Required next greater number return new string(bnumArray); } // Driver program to test above static void Main(string[] args) { string bnum = "10010"; Console.WriteLine("Binary representation of next greater number = " + NextGreaterWithSameDigits(bnum)); } }} |
Javascript
function nextGreaterWithSameDigits(bnum) { const l = bnum.length; let i = l - 1; // Find the rightmost non-trailing one while (i >= 0 && bnum[i] === '0') { i--; } if (i < 0) { return "no greater number"; } // Find the rightmost zero to the right of i let j = i - 1; while (j >= 0 && bnum[j] === '1') { j--; } if (j < 0) { return "no greater number"; } // Convert string to array for swapping bnum = bnum.split(''); // Swap the RT1 with the rightmost zero to the right of i [bnum[i], bnum[j]] = [bnum[j], bnum[i]]; // Sort the substring to the right of j in ascending order const sortedSubstring = bnum.slice(j + 1).sort().join(''); // Required next greater number return bnum.slice(0, j + 1).join('') + sortedSubstring;}// Driver program to test abovefunction main() { const bnum = "10010"; console.log("Binary representation of next greater number =", nextGreaterWithSameDigits(bnum));}main(); |
Output
Binary representation of next greater number = 10100
Time Complexity : O(n + m log m), where n is the length of the input string and m is the length of the substring to the right of the swapped characters.
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!
