資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中求陣列中和能被 K 整除的數對個數
給定一個整數型別的陣列，任務是從給定陣列中形成數對，計算數對中元素的和，並檢查給定的和是否能被 k 整除。
輸入 − int arr[] = {4, 1, 2, 0, 2}, int k = 2
輸出 − 陣列中和能被 k 整除的數對個數為 − 2
解釋 − 從給定陣列中可以形成的數對為：(4, 1) = 5（不能被 2 整除），(4, 2) = 6（能被 2 整除），(4, 0) = 4（能被 2 整除），(1, 2) = 3（不能被 2 整除），(1, 0) = 1（不能被 2 整除），(2, 0) = 2（能被 2 整除），(2, 2) = 4（能被 2 整除），(0, 2) = 2（能被 2 整除）。因此，和能被 k（2）整除的數對為 (4, 2)，(4, 0)，(2, 0)，(2, 2) 和 (0, 2)。
輸入 − int arr[] = {2, 4, 8, 6, 10} , int k = 4
輸出 − 陣列中和能被 k 整除的數對個數為 − 4
解釋 − 從給定陣列中可以形成的數對為：(2, 4) = 6（不能被 4 整除），(2, 8) = 10（不能被 4 整除），(2, 6) = 8（能被 4 整除），(2, 10) = 12（能被 4 整除），(4, 8) = 12（能被 4 整除），(4, 6) = 10（不能被 4 整除），(4, 10) = 14（不能被 4 整除），(8, 6) = 14（不能被 4 整除），(8, 10) = 18（不能被 4 整除），(6, 10) = 16（能被 4 整除）。因此，和能被 4 整除的數對為 (2, 10)，(2, 6)，(4, 8) 和 (6, 10)。
下面程式中使用的解決方法如下
解決給定問題的方法可能有多種，例如樸素方法和高效方法。所以讓我們先看看樸素方法。
輸入一個整數元素陣列和一個整數變數 k，然後計算陣列的大小並將資料傳遞給函式
宣告一個臨時變數 count 來儲存和能被 k 整除的數對的個數。
從 i 為 0 開始，迴圈到陣列大小
在迴圈內部，從 j 為 i + 1 開始，迴圈到陣列大小
在迴圈內部計算和為 arr[i] + arr[j]，並檢查 IF sum % k == 0，則將 count 加 1。
返回 count
列印結果。
高效方法
輸入一個整數元素陣列並計算陣列的大小，並將資料傳遞給函式
宣告一個臨時變數 count 來儲存和能被 k 整除的數對的個數。
建立一個大小為 k 的陣列，因為我們需要檢查是否能被 k 整除。
從 i 為 0 開始，迴圈到陣列大小
在迴圈內部，將 temp 設定為 arr[i] % k，並將陣列前置遞增為 ++check[temp]
將 count 設定為 new_arr[0] * (new_arr[0] - 1)/2
從 i 為 1 開始，迴圈到 i <= k/2 且 i != (k-i)
在迴圈內部，將 count 設定為 count + new_arr[i] * (new_arr[k - i])
檢查 IF k % 2 = 0，則將 count 設定為 count + (new_arr[k / 2] * (new_arr[k / 2] - 1) / 2)
返回 count
列印結果。
示例（樸素方法）
#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;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count pairs in array whose sum is divisible by k are: 6
示例（高效方法）
#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;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count pairs in array whose sum is divisible by k are: 6
2K+ 次瀏覽
