처음 n개의 자연수에서 두 부분집합의 합 사이의 최소 차이를 찾는 C++ 프로그램

<시간/>

숫자 n이 있다고 가정합니다. 처음 n개의 자연수를 고려하십시오. 각 원소가 정확히 하나의 집합에 속하고 A에 있는 원소의 합과 B에 있는 원소의 합 사이의 절대차가 최소가 되도록 두 집합 A와 B로 나누어 그 차이를 찾아야 합니다.

따라서 입력이 n =5와 같으면 출력은 1이 됩니다. 왜냐하면 A ={1, 3, 4} 및 B ={2, 5}로 만들면 합계 값은 8과 7이기 때문입니다. 차이는 1입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

return (n * (n + 1) / 2) mod 2

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
   return (n * (n + 1) / 2) % 2;
}
int main() {
   int n = 5;
   cout << solve(n) << endl;
}