Dada una entrada binaria que representa la representación binaria del número positivo n, busque la representación binaria del número más pequeño mayor que n con el mismo número de 1 y 0 que en la representación binaria de n. Si no se puede formar tal número, escriba «no mayor número».
La entrada binaria puede ser y puede no caber incluso en int largo largo sin signo.
Ejemplos:
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
Este problema simplemente se reduce a encontrar la siguiente permutación de una string dada. Podemos encontrar next_permutation() del número binario de entrada.
A continuación se muestra un algoritmo para encontrar la siguiente permutación en una string binaria.
- Atraviese la string binaria bstr desde la derecha.
- Mientras atraviesa, encuentre el primer índice i tal que bstr[i] = ‘0’ y bstr[i+1] = ‘1’.
- Intercambia el carácter de índice ‘i’ e ‘i+1’.
- Dado que necesitamos el siguiente valor más pequeño, considere la substring desde el índice i+2 hasta el final y mueva todos los 1 en la substring al final.
A continuación se muestra la implementación de los pasos anteriores.
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's
string 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 above
int 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's
static 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 above
public 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's
def 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 code
bnum = "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's
static 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 code
public 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's
function 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 code
let bnum = "10010".split("");
document.write("Binary representation of next " +
"greater number = " +
nextGreaterWithSameDigits(bnum));
// This code is contributed by rag2127
</script>
Producción
Binary representation of next greater number = 10100
Complejidad de tiempo: O (n) donde n es el número de bits en la entrada.
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA