문제 설명
두 개의 숫자 n과 k가 주어지면 결과 숫자가 정확히 k 세트 비트를 갖도록 비트를 뒤집음으로써 주어진 숫자를 최대화하는 데 필요한 최소 뒤집기 횟수를 찾아야 합니다. 입력은 k
예
n =9 및 k =2
9의 이진 표현은 -1001이며 4비트를 포함합니다.
2개의 세트 비트가 있는 가장 큰 4자리 이진수는 -1100, 즉 12
1001을 1100으로 변환하려면 강조 표시된 2비트를 뒤집어야 합니다.
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
알고리즘
1. Count the number of bits in n. Let us call this variable as bitCount. we can use log2(n) function from math library as fllows:
bitCount = log2(n) + 1;
2. Find largest number with k set bits as follows: maxNum = pow(2, k) - 1;
3. Find the largest number possible with k set bits and having exactly same number of bits as n as follows:
maxNum = maxNum << (bitCount - k);
4. Calculate (n ^ maxNum) and count number of set bits.
예시
#include <iostream>
#include <cmath>
using namespace std;
int getSetBits(int n){
int cnt = 0;
while (n) {
++cnt;
n = n & (n - 1);
}
return cnt;
}
int minFlipsRequired(int n, int k){
int bitCount, maxNum, flipCount;
bitCount = log2(n) + 1;
maxNum = pow(2, k) - 1;
maxNum = maxNum << (bitCount - k);
flipCount = n ^ maxNum;
return getSetBits(flipCount);
}
int main(){
cout << "Minimum required flips: " << minFlipsRequired(9, 2) << "\n";
return 0;
} 출력
Minimum required flips: 2