logo

TechCodeview

Representació binària del nombre següent més gran amb el mateix nombre d'1 i 0

Donada una entrada binària que representa la representació binària del nombre positiu n, trobeu la representació binària del nombre més petit més gran que n amb el mateix nombre d'1 i 0 que en la representació binària de n. Si no es pot formar aquest número, escriviu "cap nombre més gran".
L'entrada binària pot ser i pot no encaixar fins i tot en int long long sense 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

Aquest problema simplement es redueix a trobar la següent permutació d'una cadena determinada. Podem trobar el next_permutation() del nombre binari d'entrada. 



A continuació es mostra un algorisme per trobar la següent permutació en una cadena binària.  

  1. Travessa la cadena binària bstr des de la dreta.
  2. Mentre recorreu, busqueu el primer índex i tal que bstr[i] = '0' i bstr[i+1] = '1'.
  3. Canvi de caràcters a l'índex 'i' i 'i+1'.
  4. Com que necessitem el valor següent més petit, considereu la subcadena de l'índex i+2 per acabar i moure-ho tot 1's a la subcadena al final.

A continuació es mostra la implementació dels passos anteriors. 

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>

Sortida 
Binary representation of next greater number = 10100

Complexitat temporal: O(n) on n és el nombre de bits a l'entrada.
Espai auxiliar: O(1)

 

Enfocament 2:

Aquest és l'enfocament per trobar el següent nombre més gran amb el mateix nombre d'1 i 0 en una cadena binària:

  1. Trobeu el que no està més a la dreta (RT1) de la cadena. Sigui el seu índex i.
  2. Si no hi ha RT1, la cadena binària donada ja és la cadena binària més gran possible amb el mateix nombre d'1 i 0. Torna "cap nombre més gran".
  3. Trobeu el zero més a la dreta a la dreta de i (que el seu índex sigui j) i canvieu-lo amb RT1.
  4. Ordena la subcadena a la dreta de j en ordre ascendent.
  5. Retorna la cadena resultant.

Aquí teniu el codi C++ i Java corregit per a aquest enfocament:

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

Sortida 
Binary representation of next greater number = 10100

Complexitat temporal : O(n + m log m) on n és la longitud de la cadena d'entrada i m és la longitud de la subcadena a la dreta dels caràcters intercanviats.
Espai Auxiliar : O(n)

Crea un qüestionari