นับวิธีสร้างทริปเล็ตที่มีผลคูณน้อยที่สุด ใน C++

ได้รับอาร์เรย์ Arr[] ต้องการนับจำนวนทริปเล็ต (i

ตัวอย่าง

อินพุต: arr[] = {1, 2, 3, 2, 4, 1, 5}

เอาต์พุต: 2

คำอธิบาย: ผลคูณน้อยที่สุด = 2, ทริปเล็ต: (1,2,1) และ (1,2,1) (จาก index ที่ต่างกัน)

อินพุต: arr[] = {1, 1, 2, 1, 2, 2}

เอาต์พุต: 1 (ทริปเล็ต (1,1,1) ผลคูณ = 1)

แนวทาง

1. ลูป 3 ชั้นหา minprod (ผลคูณน้อยที่สุด)
2. ลูป 3 ชั้นอีกครั้งนับทริปเล็ตที่ผลคูณ = minprod

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

#include <bits/stdc++.h>
using namespace std;

int countTriplets(int arr[], int n) {
    int count = 0, prod = 1, minprod = 9999;
    // หาผลคูณน้อยที่สุด
    for (int i = 0; i < n-2; i++) {
        for (int j = i+1; j < n-1; j++) {
            for (int k = j+1; k < n; k++) {
                prod = arr[i] * arr[j] * arr[k];
                if (prod <= minprod) minprod = prod;
            }
        }
    }
    // นับทริปเล็ตที่มีผลคูณ = minprod
    for (int i = 0; i < n-2; i++) {
        for (int j = i+1; j < n-1; j++) {
            for (int k = j+1; k < n; k++) {
                prod = arr[i] * arr[j] * arr[k];
                if (prod == minprod) count++;
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {1, 2, 3, 1, 2, 6};
    int N = 5;
    cout << endl << "Number of triplets: " << countTriplets(Arr, N);
    return 0;
}

ผลลัพธ์

Number of triplets: 2