Chúng ta được cung cấp một mảng các phần tử kiểu số nguyên 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 đã cho có chia hết cho k hay không.
Đầu vào - int arr [] ={4, 1, 2, 0, 2}, int k =2
Đầu ra - Đếm các cặp trong mảng có tổng chia hết cho k là - 2
Giải thích - Các cặp số có thể tạo thành từ mảng đã cho là:(4, 1) =5 (không chia hết cho 2), (4, 2) =6 (chia hết cho 2), (4, 0) =4 (chia hết cho 2), (1, 2) =3 (không chia hết cho 2), (1, 0) =1 (không chia hết cho 2), (2, 0) =2 (chia hết cho 2), (2, 2) =4 (chia hết cho 2), (0, 2) =2 (chia hết cho 2). Vậy các cặp có tổng chia hết cho k là 2 là (4, 2), (4, 0), (2, 0), (2, 2) và (0, 2).
Đầu vào - int arr [] ={2, 4, 8, 6, 10}, int k =4
Đầu ra - Đếm các cặp trong mảng có tổng chia hết cho k là - 4
Giải thích - Các cặp số có thể tạo thành từ mảng đã cho là:(2, 4) =6 (không chia hết cho 4), (2, 8) =10 (không chia hết cho 4), (2, 6) =8 (chia hết cho 4), (2, 10) =12 (chia hết cho 4), (4, 8) =12 (chia hết cho 4), (4, 6) =10 (không chia hết cho 4), (4, 10) =14 (không chia hết cho 4), (8, 6) =14 (không chia hết cho 4), (8, 10) =18 (không chia hết cho 4), (6, 10) =16 (chia hết cho 4). Vậy các cặp có tổng chia hết cho 4 là (2, 10), (2, 6), (4, 8) và (6, 10).
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 gồm các phần tử nguyên và một biến số nguyên dưới dạng k, sau đó tính kích thước của mảng và truyền dữ liệu vào hàm
-
Khai báo biến đếm tạm thời để lưu trữ số lượng các cặp có tổng chia hết cho 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 tổng dưới dạng arr [i] + arr [j] và kiểm tra IF sum% k ==0, sau đó tăng số lượng lên 1.
-
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 biến đếm tạm thời để lưu trữ số lượng các cặp có tổng chia hết cho k.
-
Tạo một mảng có kích thước k vì chúng ta phải kiểm tra tính chia hết cho 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, đặt tạm thời là arr [i]% k và tăng trước mảng là ++ kiểm tra [temp]
-
Đặt số lượng là new_arr [0] * (new_arr [0] - 1) / 2
-
Bắt đầu vòng lặp FOR như tôi đến 1 cho đến khi tôi <=k / 2 VÀ i! =(K-i)
-
Bên trong vòng lặp, đặt số đếm là count + new_arr [i] * (new_arr [k - i])
-
Kiểm tra IF k% 2 =0 rồi đặt số đếm là đếm + (new_arr [k / 2] * (new_arr [k / 2] - 1) / 2)
-
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_k(int arr[], int size, int k){
int count = 0;
for(int i = 0 ;i <size ; i++){
for(int j = i+1; j<size; j++){
int sum = arr[i] + arr[j];
if(sum % k == 0){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(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 pairs in array whose sum is divisible by k are: 6
Ví dụ (Phương pháp Tiếp cận Hiệu quả)
#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
int temp = 0;
int count = 0;
int check[k] = {0};
for (int i = 0; i < size; i++){
temp = arr[i] % k;
++check[temp];
}
count = check[0] * (check[0] - 1) / 2;
for (int i = 1; i <= k / 2 && i != (k - i); i++){
count = count + check[i] * (check[k - i]);
}
if (k % 2 == 0){
count = count + (check[k / 2] * (check[k / 2] - 1) / 2);
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(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 pairs in array whose sum is divisible by k are: 6