หาจำนวนคู่ (x, y) ในอาร์เรย์ที่ทำให้ x^y > y^x ใน C++

ปัญหา

สมมติว่าเรามีอาร์เรย์สองตัว X และ Y ของจำนวนเต็มบวก จงหาจำนวนคู่ (x, y) ที่ทำให้ x^y > y^x โดยที่ x เป็นสมาชิกของ X และ y เป็นสมาชิกของ Y

ตัวอย่าง: X = [2, 1, 6], Y = [1, 5] ผลลัพธ์คือ 3 เพราะมี 3 คู่ คือ (2, 1), (2, 5) และ (6, 1)

แนวคิดการแก้ปัญหา

สามารถแก้ปัญหานี้ได้อย่างมีประสิทธิภาพโดยใช้หลักการที่ว่า "เมื่อ y > x แล้ว x^y > y^x" ซึ่งเป็นจริงในส่วนใหญ่ แต่มีบางข้อยกเว้น ต้องจัดการกรณีพิเศษเหล่านั้น

ขั้นตอนการทำงาน

• จัดเรียงอาร์เรย์ Y ให้เรียงลำดับจากน้อยไปมาก
• สำหรับแต่ละค่า x ใน X ให้หาตำแหน่งของตัวเลขที่น้อยที่สุดใน Y ที่มีค่ามากกว่า x โดยใช้ Binary Search (หรือฟังก์ชัน upper_bound)
• สมาชิกทั้งหมดหลังจากตำแหน่งที่พบจะเป็นคำตอบที่ตรงเงื่อนไข จึงนำจำนวนมาบวกเข้าไปในตัวนับ
• จัดการกรณีพิเศษของ x = 0, 1, 2, 3 แยกต่างหาก

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

#include <iostream>
#include <algorithm>
using namespace std;

int count(int x, int Y[], int n, int no_of_y[]) {
    if (x == 0) return 0;
    if (x == 1) return no_of_y[0];
    
    int* index = upper_bound(Y, Y + n, x);
    int ans = (Y + n) - index;
    
    ans += (no_of_y[0] + no_of_y[1]);
    
    if (x == 2) ans -= (no_of_y[3] + no_of_y[4]);
    if (x == 3) ans += no_of_y[2];
    
    return ans;
}

int howManyPairs(int X[], int Y[], int m, int n) {
    int no_of_y[5] = {0};
    for (int i = 0; i < n; i++)
        if (Y[i] < 5)
            no_of_y[Y[i]]++;
    
    sort(Y, Y + n);
    
    int total_pairs = 0;
    for (int i = 0; i < m; i++)
        total_pairs += count(X[i], Y, n, no_of_y);
    
    return total_pairs;
}

int main() {
    int X[] = {2, 1, 6};
    int Y[] = {1, 5};
    int m = sizeof(X)/sizeof(X[0]);
    int n = sizeof(Y)/sizeof(Y[0]);
    cout << "Total pair count: " << howManyPairs(X, Y, m, n);
}

ผลลัพธ์

Total pair count: 3