ขั้นตอนต่ำสุดเพื่อทำให้ทุกองค์ประกอบในอาเรย์หารด้วย 4 ลงตัวใน C++

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

กำหนดอาเรย์ขนาด n งานคือหาจำนวนขั้นตอนต่ำสุดที่จำเป็นเพื่อทำให้ทุกองค์ประกอบในอาเรย์หารด้วย 4 ลงตัว ขั้นตอนหนึ่งถูกนิยามว่าเป็นการลบองค์ประกอบสองตัวใดก็ได้จากอาเรย์และเพิ่มผลรวมขององค์ประกอบเหล่านั้นเข้าไปในอาเรย์

ตัวอย่าง

ถ้าอาเรย์อินพุตคือ {1, 2, 0, 2, 4, 3} แล้วต้องใช้ 3 การดำเนินการ -

1 + 3 = 4
2 + 2 = 4
0 + 4 = 4

อัลกอริทึม

1. ผลรวมของทุกองค์ประกอบในอาเรย์ควรหารด้วย 4 ลงตัว ถ้าไม่ใช่ งานนี้เป็นไปไม่ได้
2. เริ่มต้นอาเรย์ชื่อ modulus ขนาด 4 เป็น 0
3. เริ่มต้นตัวนับเป็น 0 จะติดตามจำนวนขั้นตอนที่ทำ
4. วนลูปผ่านอาเรย์อินพุตและหา modulus 4 ของแต่ละองค์ประกอบ
5. เพิ่มค่าของ mod 4 ในอาเรย์ modulus ขึ้น 1
6. modulus[0] คือจำนวนองค์ประกอบที่หารด้วย 4 ลงตัวแล้ว จึงไม่ต้องจับคู่กับองค์ประกอบอื่น
7. modulus[1] และ modulus[3] สามารถรวมกันได้เลขที่หารด้วย 4 ลงตัว ดังนั้นเพิ่มตัวนับเป็นค่าต่ำสุดของทั้งสอง
8. ทุก 2 องค์ประกอบของ modulus[2] สามารถรวมกันได้องค์ประกอบที่หารด้วย 4 ลงตัว
9. สำหรับองค์ประกอบที่เหลือ เพิ่มค่า modulus[2] ด้วยครึ่งหนึ่งของ modulus[1] และ modulus[3]
10. ตอนนี้ เพิ่มตัวนับด้วยครึ่งหนึ่งของ modulus[2] เราหยิบครึ่งเพราะทุก 2 องค์ประกอบรวมเป็น 1
11. ค่าสุดท้ายของตัวนับคือจำนวนขั้นตอนที่จำเป็นในการแปลงทุกองค์ประกอบของอาเรย์อินพุทให้หารด้วย 4 ลงตัว

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

#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(int arr[], int n) {
  int count = 0;
  int modulus[4] = {0};
  int sum = 0;
  for (int i = 0; i < n; i++) {
    int mod = arr[i] % 4;
    sum += mod;
    modulus[mod]++;
  }
  if (sum % 4 != 0) {
    return -1;
  } else {
    if (modulus[1] > modulus[3]) {
      count += modulus[3];
    } else {
      count += modulus[1];
    }
    modulus[1] -= count;
    modulus[3] -= count;
    modulus[2] += modulus[1] / 2;
    modulus[2] += modulus[3] / 2;
    count += modulus[1] / 2;
    count += modulus[3] / 2;
    count += modulus[2] / 2;
    return count;
  }
}
int main() {
  int arr[] = {1, 2, 0, 2, 4, 3};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Minimum required steps = " << getMinRequiredSteps(arr, n) << endl;
  return 0;
}

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

ผลลัพธ์

Minimum required steps = 2