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

สมมติว่ามีอาร์เรย์ n องค์ประกอบ อัปเดตทุกองค์ประกอบของอาร์เรย์ที่กำหนดให้เป็นค่า x ต่ำสุด ซึ่ง arr[i] = x ซึ่งผลคูณของทุกองค์ประกอบในอาร์เรย์ใหม่จะมากกว่าผลคูณของทุกองค์ประกอบของอาร์เรย์เริ่มต้นอย่างเคร่งครัด โดยที่ i <= arr[i] <= 10^10 และ 1 <= n <= 10^5 ดังนั้นถ้าอาร์เรย์เป็น [4, 2, 1, 10, 6] 4 คือองค์ประกอบน้อยที่สุด 4 * 4 * 4 * 4 * 4 > 4 * 2 * 1 * 10 * 6

เรารู้ว่าผลคูณของ n องค์ประกอบคือ P หากเราต้องการหารากที่ n ของ P เพื่อหารากที่ n ของผลคูณ เราเพียงแค่หาร n จากผลรวมของ log ของ n องค์ประกอบของอาร์เรย์ และจากนั้น ceiling ของ antilog จะเป็นผลลัพธ์

res = ceil(antilog(log(x) / 10))

หรือ res = ceil(10 ^ (log(x) / 10))

ตัวอย่าง

#include <iostream> 
#include <cmath> 
#define EPS 1e-15 
using namespace std; 

long long findMinValue(long long arr[], long long n) {
    long double sum = 0;
    for (int i = 0; i < n; i++)
        sum += (long double)log10(arr[i]) + EPS;
    long double xl = (long double)(sum / n + EPS);
    long double res = pow((long double)10.0, (long double)xl) + EPS;
    return (long long)ceil(res + EPS);
}

int main() {
    long long arr[] = {4, 2, 1, 10, 6};
    long long n = sizeof(arr) / sizeof(arr[0]);
    cout << "Min value is: " << findMinValue(arr, n);
}

ผลลัพธ์

Min value is: 4