โปรแกรม C ++ เพื่อค้นหาความแตกต่างขั้นต่ำระหว่างผลรวมของสองชุดย่อยจาก n ตัวเลขธรรมชาติตัวแรก

สมมติว่าเรามีตัวเลข 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;
}