การลบองค์ประกอบน้อยที่สุดเพื่อให้ผลรวมอาเรย์เป็นคี่ใน C++

ข้อกำหนดโจทย์

กำหนดอาเรย์ arr[] ของจำนวนเต็ม N ตัว เราต้องเขียนโปรแกรมเพื่อหาจำนวนองค์ประกอบน้อยที่สุดที่ต้องลบออกจากอาเรย์ เพื่อให้ผลรวมขององค์ประกอบที่เหลือเป็นเลขคี่

ตัวอย่าง

ถ้าอาเรย์อินพุตคือ {10, 20, 30, 5, 7} แล้วเราต้องลบหนึ่งองค์ประกอบ คือ 5 หรือ 7 เพื่อให้ผลรวมอาเรย์เป็นคี่

อัลกอริทึม

1. ผลรวมของจำนวนคู่กี่ตัวก็ตามจะเป็นคู่เสมอ
2. ผลรวมของจำนวนคี่จำนวนคี่ครั้งจะเป็นคี่เสมอ
3. ผลรวมของจำนวนคี่จำนวนคู่ครั้งจะเป็นคู่เสมอ
4. นับจำนวนองค์ประกอบคี่ในอาเรย์ ถ้าจำนวนคี่เป็นเลขคู่ เราต้องลบองค์ประกอบเดียวจากอาเรย์ แต่ถ้าจำนวนคี่เป็นเลขคี่ ไม่ต้องลบองค์ประกอบใดๆ

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

#include <bits/stdc++.h>
using namespace std;
int getMinRemovals(int *arr, int n) {
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (arr[i] % 2 == 1) {
      ++cnt;
    }
  }
  return (cnt % 2 == 0) ? 1 : 0;
}
int main() {
  int arr[] = {10, 20, 30, 5, 7};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Minimum required removals = " << getMinRemovals(arr, n) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum required removals = 1