สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ เราต้องหาความยาวของสับเซต (subset) ที่ไม่ว่างขององค์ประกอบที่ผลรวมเป็นเลขคู่ หรือคืนค่า -1 เมื่อไม่มีสับเซตดังกล่าว
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [1, 3, 7] ผลลัพธ์จะได้ 2 เพราะผลรวมของ [1, 3] คือ 4
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
n := ขนาดของ A สำหรับ i := 0 เมื่อ i < n เพิ่ม i ทีละ 1 ทำ: ถ้า A[i] mod 2 เท่ากับ 0 แล้ว: k := i + 1 ถ้า n เป็น 1 และ k เป็น 0 แล้ว: คืนค่า -1 มิฉะนั้นเมื่อ k ไม่เท่ากับ 0 แล้ว: คืนค่า 1 มิฉะนั้น คืนค่า 2
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A) { long n = A.size(), k = 0; for (long i = 0; i < n; i++) { if (A[i] % 2 == 0) { k = i + 1; } } if (n == 1 & k == 0) { return -1; } else if (k != 0) { return 1; } else { return 2; } } int main() { vector<int> A = { 1, 3, 7 }; cout << solve(A) << endl; }
ข้อมูลนำเข้า
{ 1, 3, 7 }
ข้อมูลส่งออก
2
