logo

TechCodeview

Representación binaria del siguiente número mayor con el mismo número de unos y ceros

Dada una entrada binaria que representa la representación binaria del número positivo n, encuentre la representación binaria del número más pequeño mayor que n con el mismo número de unos y ceros que en la representación binaria de n. Si no se puede formar ese número, imprima "ningún número mayor".
La entrada binaria puede caber o no incluso en un 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 cadena determinada. Podemos encontrar el siguiente_permutación() del número binario de entrada. 



A continuación se muestra un algoritmo para encontrar la siguiente permutación en una cadena binaria.  

  1. Atravesar la cadena binaria bstr desde la derecha.
  2. Mientras recorre encuentre el primer índice. i tal que bstr[i] = '0' y bstr[i+1] = '1'.
  3. Carácter de intercambio del índice 'i' e 'i+1'.
  4. Dado que necesitamos el siguiente valor más pequeño, considere la subcadena del índice yo+2 para terminar y mover todo 1 en la subcadena 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    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  
');    // 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 del tiempo: O(n) donde n es el número de bits en la entrada.
Espacio auxiliar: O(1)

 

Enfoque 2:

Este es el método para encontrar el siguiente número mayor con el mismo número de unos y ceros en una cadena binaria:

  1. Encuentre el que no está más a la derecha (RT1) en la cadena. Sea su índice i.
  2. Si no hay RT1, entonces la cadena binaria dada ya es la cadena binaria más grande posible con el mismo número de unos y ceros. Devuelve 'ningún número mayor'.
  3. Encuentre el cero más a la derecha de i (sea su índice j) y cámbielo con el RT1.
  4. Ordene la subcadena a la derecha de j en orden ascendente.
  5. Devuelve la cadena resultante.

Aquí está el código C++ y Java corregido para este enfoque:

C++ 
#include    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 = 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 above int 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's def 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 function if __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 above function main() {  const bnum = '10010';  console.log('Binary representation of next greater number =' nextGreaterWithSameDigits(bnum)); } main();

Producción 
Binary representation of next greater number = 10100

Complejidad del tiempo : O(n + m log m) donde n es la longitud de la cadena de entrada y m es la longitud de la subcadena a la derecha de los caracteres intercambiados.
Espacio Auxiliar : En)

Crear cuestionario