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ổng các phần tử trong cặp và kiểm tra xem tổng được tính có nhỏ hơn x hay không.
Đầu vào - int arr [] ={2, 7, 1, 0, 8}, int x =8
Đầu ra - Đếm các cặp trong một mảng đã sắp xếp có tổng nhỏ hơn x là - 4
Giải thích - Các cặp có thể tạo thành từ mảng đã cho là:(2, 7) =9 (lớn hơn x), (2, 1) =3 (nhỏ hơn x), (2, 0) =2 (nhỏ hơn x ), (2, 8) =10 (lớn hơn x), (7, 1) =8 (bằng x), (7, 0) =7 (nhỏ hơn x), (7, 8) =15 (lớn hơn hơn x), (1, 0) =1 (nhỏ hơn x), (1, 8) =8 (bằng x), (0, 8) =8 (bằng x). Vậy các cặp có tổng nhỏ hơn x là (4, 0) và (2, 2). Vì vậy, số cặp có tổng nhỏ hơn x là 4.
Đầu vào - int arr [] ={2, 4, 6, 8}, int x =10
Đầu ra - Đếm các cặp trong một mảng đã sắp xếp có tổng nhỏ hơn x là - 2
Giải thích - Các cặp có thể tạo thành từ mảng đã cho là:(2, 4) =6 (nhỏ hơn x), (2, 6) =8 (nhỏ hơn x), (2, 8) =10 (bằng x ), (4, 6) =10 (bằng x), (4, 8) =12 (lớn hơn x), (6, 8) =14 (lớn hơn x). Vì vậy, số cặp có tổng nhỏ hơn x là 2.
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ố đếm biến tạm thời để lưu trữ số lượng các cặp có tổng nhỏ hơn x.
-
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 tổng dưới dạng arr [i] + arr [j] và kiểm tra IF sum
-
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_sum(int arr[], int size, int x){
int count = 0;
int sum = 0;
for(int i = 0 ;i <size ; i++){
for(int j = i+1; j<size; j++){
sum = arr[i] + arr[j];
if(sum < x){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {2, 7, 1, 0, 8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
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 sum is less than x are: 4
Ví dụ (Cách tiếp cận hiệu quả)
#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
int arr_0 = 0;
int arr_1 = size-1;
int count = 0;
while(arr_0 < arr_1){
if (arr[arr_0] + arr[arr_1] < x){
count = count + (arr_1 - arr_0);
arr_0++;
}
else{
arr_1--;
}
}
return count;
}
int main(){
int arr[] = {2, 7, 1, 0, 8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
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 sum is less than x are: 4