logo

TechCodeview

Représentation binaire du prochain plus grand nombre avec le même nombre de 1 et de 0

Étant donné une entrée binaire qui représente la représentation binaire du nombre positif n, trouvez la représentation binaire du plus petit nombre supérieur à n avec le même nombre de 1 et de 0 que dans la représentation binaire de n. Si aucun nombre de ce type ne peut être formé, inscrivez « pas de nombre supérieur ».
L'entrée binaire peut être et ne peut pas tenir même dans un entier long non signé.

Exemples :  

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

Ce problème se résume simplement à trouver la prochaine permutation d’une chaîne donnée. Nous pouvons trouver le prochaine_permutation() du nombre binaire d’entrée. 



Vous trouverez ci-dessous un algorithme pour trouver la prochaine permutation dans une chaîne binaire.  

c booléen
  1. Parcourez la chaîne binaire bstr de la droite.
  2. En parcourant, trouvez le premier index je tel que bstr[i] = '0' et bstr[i+1] = '1'.
  3. Caractère d'échange de l'index 'i' et 'i+1'.
  4. Puisque nous avons besoin de la plus petite valeur suivante, considérons la sous-chaîne de l'index je+2 pour finir et tout déplacer 1 dans la sous-chaîne à la fin.

Vous trouverez ci-dessous la mise en œuvre des étapes ci-dessus. 

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>

Sortir 
Binary representation of next greater number = 10100

Complexité temporelle : O(n) où n est le nombre de bits en entrée.
Espace auxiliaire : O(1)

 

Approche 2 :

Voici l'approche pour trouver le nombre immédiatement supérieur avec le même nombre de 1 et de 0 dans une chaîne binaire :

  1. Recherchez celui qui se trouve le plus à droite (RT1) dans la chaîne. Soit son indice i.
  2. S'il n'y a pas de RT1, alors la chaîne binaire donnée est déjà la plus grande chaîne binaire possible avec le même nombre de 1 et de 0. Renvoie « pas de nombre supérieur ».
  3. Trouvez le zéro le plus à droite de i (que son index soit j) et échangez-le avec le RT1.
  4. Triez la sous-chaîne à droite de j par ordre croissant.
  5. Renvoie la chaîne résultante.

Voici le code C++ et Java corrigé pour cette approche :

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();

Sortir 
Binary representation of next greater number = 10100

Complexité temporelle : O(n + m log m) où n est la longueur de la chaîne d'entrée et m est la longueur de la sous-chaîne à droite des caractères échangés.
Espace auxiliaire : Sur)

Créer un quiz