이 문제에서 정수 값 N이 주어집니다. 우리의 임무는 다음 예비 번호를 찾는 프로그램을 만드는 것입니다.
희소 숫자 이진 변환에 인접한 1이 포함되지 않는 특수 유형의 숫자입니다.
Example: 5(101) , 16(10000)
문제 설명 − 주어진 숫자 N에 대해 희소 숫자인 N보다 큰 가장 작은 숫자를 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
N = 7
출력
8
설명
8의 이진수는 1000이므로 n보다 큰 가장 작은 희소 숫자입니다.
해결 방법
문제에 대한 간단한 해결책은 N보다 큰 모든 숫자를 확인하고 첫 번째 희소 숫자를 찾을 때까지 중지하는 것입니다.
이를 위해 우리는 N에서 무한대로 반복하고 각 숫자에 대해 희소 숫자인지 여부를 확인해야 합니다. 그렇다면 루프를 끊고 그렇지 않으면 계속하십시오.
우리 솔루션의 작동을 설명하는 프로그램
예
#include<iostream>
using namespace std;
bool isSpareNumber(int N){
int currentBit = (N&1);
int nextBit ;
while (N!= 0){
nextBit = currentBit;
currentBit = (N&1);
N >>= 1;
if(nextBit == currentBit && nextBit == 1 && currentBit == 1)
return false ;
}
return true;
}
int findNextSparseNumber(int N) {
while(1){
if(isSpareNumber(N))
return N;
N++;
}
return -1;
}
int main() {
int N = 564;
cout<<"The number is "<<N<<endl;
cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
return 0;
} 출력
The number is 564 The next Sparse Number is 576
효율적인 접근
문제에 대한 효율적인 접근 방식은 숫자의 비트를 조작하는 것입니다. 이를 위해 숫자의 이진법을 찾고 인접성이 발생하는 비트를 조작합니다. 최하위 비트에서 최상위 비트로 순회하면서 한 쌍의 1을 만나면 두 1을 모두 0으로 바꾸고 다음 비트를 1로 만듭니다. 그리고 MSB에 도달할 때까지 이 작업을 수행합니다. 그런 다음 숫자 이진수를 우리의 결과인 십진수로 다시 변환합니다.
여기서 예를 들어보겠습니다.
N =52
숫자의 2진수는 110100입니다.
우리는 LSB에서 순회하고 이진법에서 연속 1의 첫 번째 쌍을 찾습니다. 11입니다. 0100 강조 표시된 부분. 그런 다음 1을 모두 0으로 바꾸고 다음 비트에 1을 추가합니다. 이렇게 하면 이진 변환이 64인 숫자가 1000000이 됩니다. .
우리 솔루션의 작동을 설명하는 프로그램
예
#include<iostream>
using namespace std;
int findNextSparseNumber(int N) {
int spNum[16];
int n = 0;
while (N != 0) {
spNum[n] = (N&1);
n++;
N >>= 1;
}
n++;
int lastCorrectedBit = 0;
for (int i= 0 ; i< n; i++) {
if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1){
spNum[i+1] = 1;
for (int j=i; j>=lastCorrectedBit; j--)
spNum[j] = 0;
lastCorrectedBit = i+1;
}
}
int sparseNumber = 0;
for (int i =0; i<n-1; i++)
sparseNumber += spNum[i]*(1<<i);
return sparseNumber;
}
int main() {
int N = 564;
cout<<"The number is "<<N<<endl;
cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
return 0;
} 출력
The number is 564 The next Sparse Number is 576