Chương trình C ++ để tìm hiệu số nhỏ nhất giữa tổng của hai tập con từ n số tự nhiên đầu tiên

Giả sử chúng ta có một số n. Xét n số tự nhiên đầu tiên. Chúng ta phải chia chúng thành hai tập hợp A và B sao cho mỗi phần tử thuộc đúng một tập hợp và hiệu số tuyệt đối giữa tổng các phần tử trong A và tổng các phần tử trong B là nhỏ nhất, và tìm hiệu số đó.

Vì vậy, nếu đầu vào là n =5, thì đầu ra sẽ là 1, bởi vì nếu chúng ta đặt A ={1, 3, 4} và B ={2, 5}, thì các giá trị tổng là 8 và 7, vì vậy chênh lệch là 1.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

5

Đầu ra

1