하나의 숫자 N이 주어집니다. 목표는 0부터 N 사이의 수 중에서 N과의 차이(N − i)가 N과의 XOR(i ^ N)과 같아지는 수의 개수를 찾는 것입니다.
가장 단순한 방법은 i를 0부터 N까지 하나씩 순회하면서 각 i에 대해 (N − i) == (i ^ N) 조건을 검사하고, 조건을 만족할 때마다 카운트를 증가시키는 것입니다.
예시
- 입력 − N = 6
출력 − N과의 차이가 N과의 XOR과 같은 숫자의 개수: 4
설명 − 해당 숫자는 0, 2, 4, 6입니다. - 입력 − N = 20
출력 − N과의 차이가 N과의 XOR과 같은 숫자의 개수: 4
설명 − 해당 숫자는 0, 4, 16, 20입니다.
풀이 접근 방법
- 정수 N을 입력으로 받습니다.
- diffisXOR(int n) 함수는 n을 전달받아 조건을 만족하는 수의 개수를 반환합니다.
- 카운트(count)를 0으로 초기화합니다.
- i를 0부터 n까지 순회합니다.
- (n − i) == (i ^ n)이 성립하면 카운트를 1 증가시킵니다.
- 반복문이 종료되면 count에 원하는 결과가 저장되어 있습니다.
- count를 반환한 뒤 출력합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int diffisXOR(int n){
int count = 0;
for (int i = 0; i <= n; i++){
// 차이(n - i)와 XOR(i ^ n)이 같은지 확인
if((n - i) == (i ^ n))
{ count++; }
}
return count;
}
int main(){
int N = 15;
int nums = diffisXOR(N);
cout << endl << "N과의 차이가 N과의 XOR과 같은 숫자의 개수: " << nums;
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 생성됩니다 −
N과의 차이가 N과의 XOR과 같은 숫자의 개수: 16
참고: O(1) 최적화 팁
흥미롭게도 이 문제는 반복문 없이 상수 시간에 해결할 수도 있습니다. (N − i) == (N ^ i)가 성립하려면 뺄셈 과정에서 자리내림이 발생하지 않아야 하는데, 이는 i의 이진수 비트들이 N의 비트들에 완전히 포함되는 경우, 즉 i가 N의 부분 마스크일 때만 가능합니다.
따라서 정답은 항상 2^(N의 이진 표현에서 1의 개수)와 같습니다. 예를 들어 N = 15(이진수 1111)는 1비트가 4개이므로 2⁴ = 16개이고, N = 6(이진수 110)은 1비트가 2개이므로 2² = 4개가 됩니다.