การดำเนินการน้อยที่สุดเพื่อทำให้ทุกองค์ประกอบในอาเรย์เท่ากันใน C++

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

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

ตัวอย่าง

ถ้าอาเรย์อินพุตคือ = {1, 2, 3, 4} แล้วเราต้องการการดำเนินการขั้นต่ำ 3 ครั้งเพื่อทำให้ทุกองค์ประกอบเท่ากัน ตัวอย่างเช่น เราสามารถทำให้องค์ประกอบเป็น 4 โดยการบวก 3 ครั้ง

อัลกอริทึม

1. เลือกองค์ประกอบที่มีความถี่สูงสุด เรียกมันว่า 'x'
2. ตอนนี้เราต้องดำเนินการ n-x ครั้ง เพราะมี x องค์ประกอบที่มีค่าเท่ากัน

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

#include <bits/stdc++.h>
using namespace std;
int getMinOperations(int *arr, int n) {
  unordered_map<int, int> hash;
  for (int i = 0;i < n; ++i) {
    hash[arr[i]]++;
  }
  int maxFrequency = 0;
  for (auto elem : hash) {
    if (elem.second > maxFrequency) {
      maxFrequency = elem.second;
    }
  }
  return (n - maxFrequency);
}
int main() {
  int arr[] = {1, 2, 3, 4};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Minimum required operations = " << getMinOperations(arr, n) << endl;
  return 0;
}

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

ผลลัพธ์

Minimum required operations = 3