logo

TechCodeview

Binær repræsentation af næste større tal med samme antal 1'ere og 0'ere

Givet et binært input, der repræsenterer binær repræsentation af positivt tal n, find binær repræsentation af mindste tal større end n med samme antal 1'ere og 0'er som i binær repræsentation af n. Hvis der ikke kan dannes et sådant nummer, udskriv "intet større antal".
Det binære input kan være og kan ikke passe selv i unsigned long long int.

Eksempler: 

java array dynamisk 
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

Dette problem koger simpelthen ned til at finde næste permutation af en given streng. Vi kan finde næste_permutation() af det indgående binære tal. 



Nedenfor er en algoritme til at finde næste permutation i binær streng.  

  1. Gå gennem den binære streng bstr fra højre.
  2. Find det første indeks, mens du krydser jeg sådan at bstr[i] = '0' og bstr[i+1] = '1'.
  3. Udskift karakter af ved indeks 'i' og 'i+1'.
  4. Da vi har brug for den mindste næste værdi, overvej understreng fra indeks i+2 at afslutte og flytte alle 1'er i understrengen til sidst.

Nedenfor er implementeringen af ​​ovenstående trin. 

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>

Produktion 
Binary representation of next greater number = 10100

Tidskompleksitet: O(n) hvor n er antallet af bits i input.
Hjælpeplads: O(1)

binært søgetræ]

 

Fremgangsmåde 2:

Her er fremgangsmåden til at finde det næste større tal med det samme antal 1'ere og 0'ere i en binær streng:

  1. Find den ikke-slæbende længst til højre (RT1) i strengen. Lad dets indeks være i.
  2. Hvis der ikke er nogen RT1, er den givne binære streng allerede den størst mulige binære streng med det samme antal 1'ere og 0'ere. Returner 'intet større tal'.
  3. Find det yderste højre nul til højre for i (lad dets indeks være j), og skift det med RT1.
  4. Sorter understrengen til højre for j i stigende rækkefølge.
  5. Returner den resulterende streng.

Her er den korrigerede C++- og Java-kode til denne tilgang:

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

Produktion 
Binary representation of next greater number = 10100

Tidskompleksitet : O(n + m log m) hvor n er længden af ​​inputstrengen og m er længden af ​​understrengen til højre for de ombyttede tegn.
Hjælpeplads : O(n)

Opret Quiz