Chúng ta được cung cấp một mảng đã sắp xếp gồm các phần tử kiểu số nguyên và một biến số nguyên x và nhiệm vụ là tạo các cặp từ mảng đã cho và tính tích của các phần tử trong cặp và kiểm tra xem tích được tính có nhỏ hơn k hay không.
Đầu vào
int arr[] = {2, 7, 1, 0, 8}, int k = 10 Đầu ra
Count of pairs in a sorted array whose product is less than k are: 7
Giải thích
The pairs that can be formed from the given array are: (2, 7) = 14(greater than k), (2, 1) = 2(less than k), (2, 0) = 0(less than k), (2, 8) = 16(greater than k), (7, 1) = 7(less than k), (7, 0) = 0(less than k), (7, 8) = 56(greater than k), (1, 0) = 0(less than k), (1, 8) = 8(less than k), (0, 8) = 0(less than k). So, the count of pairs with sum less than k are 7.
Đầu vào
int arr[] = {2, 4, 6, 8}, int k = 10 Đầu ra
Count of pairs in a sorted array whose product is less than k are: 1
Giải thích
The pairs that can be formed from the given array are: (2, 4) = 8(less than k), (2, 6) = 12(greater than k), (2, 8) = 16(greater than k), (4, 6) = 24(greater than x), (4, 8) = 32(greater than k), (6, 8) = 48(greater than k). So, the count of pairs with products less than k is 1.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Có thể có nhiều cách tiếp cận để giải quyết vấn đề đã cho, tức là cách tiếp cận ngây thơ và cách tiếp cận hiệu quả. Vì vậy, trước tiên chúng ta hãy xem xét cách tiếp cận ngây thơ .
-
Nhập một mảng các phần tử số nguyên và tính toán kích thước của một mảng và truyền dữ liệu vào hàm
-
Khai báo số lượng biến tạm thời để lưu trữ số lượng các cặp có sản phẩm nhỏ hơn k.
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng
-
Bên trong vòng lặp, bắt đầu một vòng lặp FOR khác từ j đến i + 1 cho đến khi kích thước của một mảng
-
Bên trong vòng lặp, hãy tính toán sản phẩm dưới dạng arr [i] * arr [j] và kiểm tra IF product
-
Trả lại số lượng
-
In kết quả.
Cách tiếp cận hiệu quả
-
Nhập một mảng các phần tử số nguyên và tính toán kích thước của một mảng và truyền dữ liệu vào hàm
-
Khai báo số đếm biến tạm thời để lưu trữ số lượng các cặp có tổng nhỏ hơn x.
-
Đặt arr_0 là 0 và arr_1 là size-1
-
Bắt đầu vòng lặp FOR từ arr_0 đến arr_1
-
Bên trong vòng lặp, kiểm tra IF arr [arr_0] * arr [arr_1]
-
Trả lại số lượng
-
In kết quả.
Ví dụ (cách tiếp cận ngây thơ)
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int count = 0;
int product = 1;
for(int i = 0 ; i<size ; i++){
for(int j = i+1; j<size; j++){
product = arr[i] * arr[j];
if(product < k){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {5, 8, 2, 1, 3};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 10;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs in a sorted array whose product is less than k are: 5
Ví dụ (Cách tiếp cận hiệu quả)
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int arr_0 = 0;
int arr_1 = size-1;
int count = 0;
int product = 1;
while(arr_0 < arr_1){
product = arr[arr_0] * arr[arr_1];
if (product < k){
count = count + (arr_1 - arr_0);
arr_0++;
}
else{
arr_1--;
}
}
return count;
}
int main(){
int arr[] = {1, 3, 4, 2, 1};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs in a sorted array whose product is less than k are: 10