การตรวจสอบความเป็นไปได้ของการแบ่งเซตจาก N จำนวนธรรมชาติแรก ให้ผลต่างเป็น D ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มสองจำนวนคือ N และ D งานของเราคือตรวจสอบว่าสามารถแบ่งเซตของ N จำนวนธรรมชาติแรกออกเป็นสองเซต ที่มีผลต่างของผลรวมเท่ากับ D ได้หรือไม่

ตัวอย่าง

Input − N=5, D=3

Output − Yes

คำอธิบาย −

จาก 1, 2, 3, 4, 5 สามารถแบ่งเป็นเซต set1 = {1, 2, 3} และ set2 = {4, 5} ได้ ซึ่งให้ผลต่าง 3
{4+5} - {1+2+3} = 9 - 6 = 3

วิธีแก้ปัญหา

เราสามารถแก้ปัญหานี้ได้โดยใช้คณิตศาสตร์พื้นฐาน:

ผลรวมของจำนวนธรรมชาติ N ตัวแรก คือ sum = N(N+1)/2

ให้ผลรวมของเซตแรกเป็น sum(s1) และเซตที่สองเป็น sum(s2)

เรามีสมการสองสมการ:

sum(s1) + sum(s2) = N(N+1)/2
sum(s1) - sum(s2) = D

เมื่อรวมสมการทั้งสอง จะได้:

2 * sum(s1) = N(N+1)/2 + D

ดังนั้น เงื่อนไขที่ทำให้มีคำตอบคือ N(N+1)/2 + D ต้องเป็นจำนวนคู่ (หาร 2 ลงตัว)

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

bool isSetPossible(int N, int D) {
    int total = (N * (N + 1)) / 2 + D;
    return (total % 2 == 0);
}

int main() {
    int N = 10;
    int D = 7;
    cout << "Creating two sets from first " << N 
         << " natural numbers with difference " << D << " is ";
    isSetPossible(N, D) ? cout << "possible" : cout << "not possible";
    return 0;
}

ผลลัพธ์

Creating two sets from first 10 natural numbers with difference 7 is possible