logo

TechCodeview

1과 0의 개수가 동일한 다음으로 큰 수의 이진 표현

양수 n의 이진 표현을 나타내는 이진 입력이 주어지면 n의 이진 표현에서와 동일한 수의 1과 0을 갖는 n보다 큰 가장 작은 수의 이진 표현을 찾습니다. 그러한 숫자가 형성될 수 없으면 '더 큰 숫자 없음'을 인쇄하십시오.
이진 입력은 unsigned long long int에도 맞을 수도 있고 맞지 않을 수도 있습니다.

예:  

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

이 문제는 단순히 주어진 문자열의 다음 순열을 찾는 것으로 요약됩니다. 우리는 찾을 수 있습니다 다음_순열() 입력 이진수. 



다음은 이진 문자열에서 다음 순열을 찾는 알고리즘입니다.  

  1. 바이너리 문자열 탐색 bstr 오른쪽에서.
  2. 순회하는 동안 첫 번째 인덱스를 찾습니다. 나 bstr[i] = '0' 및 bstr[i+1] = '1'이 됩니다.
  3. 인덱스 'i'와 'i+1'의 문자를 교환합니다.
  4. 가장 작은 다음 값이 필요하므로 인덱스의 하위 문자열을 고려하십시오. 나는+2 끝내고 모두 이동하려면 1의 결국 하위 문자열에 있습니다.

다음은 위 단계의 구현입니다. 

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>

산출 
Binary representation of next greater number = 10100

시간복잡도 : O(n) 여기서 n은 입력의 비트 수입니다.
보조 공간: O(1)

 

접근법 2:

이진 문자열에서 1과 0의 수가 동일한 다음으로 큰 숫자를 찾는 방법은 다음과 같습니다.

  1. 문자열에서 맨 오른쪽 비후행 항목(RT1)을 찾습니다. 그 지수를 i라고 하자.
  2. RT1이 없으면 주어진 이진 문자열은 이미 동일한 수의 1과 0을 가진 가장 큰 이진 문자열입니다. '더 큰 숫자 없음'을 반환합니다.
  3. i 오른쪽에 있는 가장 오른쪽 0을 찾아(인덱스를 j로 설정) 이를 RT1과 교환합니다.
  4. j의 오른쪽에 있는 부분 문자열을 오름차순으로 정렬합니다.
  5. 결과 문자열을 반환합니다.

이 접근 방식에 대해 수정된 C++ 및 Java 코드는 다음과 같습니다.

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

산출 
Binary representation of next greater number = 10100

시간 복잡도 : O(n + m log m) 여기서 n은 입력 문자열의 길이이고 m은 교체된 문자 오른쪽에 있는 하위 문자열의 길이입니다.
보조 공간 : 에)

퀴즈 만들기