เราได้รับอาร์เรย์ของจำนวนบวก n ตัว เป้าหมายคือการนับคู่ที่เรียงลำดับ (arr[x], arr[y]) ด้วยผลรวมของ arr[x] และ arr [y] เป็นคู่หรือคี่ คู่ ( arr[i],arr[j] ) และ ( arr[j],arr[i] จะถูกนับแยกกัน
เราจะสำรวจอาร์เรย์โดยใช้สองลูปสำหรับจำนวนคู่แต่ละคู่ ตอนนี้ให้คำนวณผลรวม หากเป็นการเพิ่มจำนวนคู่ให้นับเป็น 2 สำหรับผลรวมคู่ ให้นับการเพิ่มทีละ 2 สำหรับผลรวมคี่
มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล − Arr[]={ 1,1,2,3 } N=4
ผลผลิต − การนับผลรวมของผลคูณคู่ − 6 การนับคู่ผลรวมคี่ − 6
คำอธิบาย − คู่ผลรวมคี่ที่ถูกต้องคือ -
Arr[0] & Arr[1] → (1,1) Arr[1] & Arr[0] → (1,1) count=2 Arr[0] & Arr[3] → (1,3) Arr[3] & Arr[0] → (3,1) count=2 Arr[1] & Arr[3] → (1,3) Arr[3] & Arr[1] → (3,1) count=2 Total=6 Valid even sum pairs are: Arr[0] & Arr[2] → (1,2) Arr[2] & Arr[0] → (2,1) count=2 Arr[1] & Arr[2] → (1,2) Arr[2] & Arr[1] → (2,1) count=2 Arr[2] & Arr[3] → (2,3) Arr[3] & Arr[2] → (3,2) count=2 Total=6
ป้อนข้อมูล − Arr[]={ 2,2,2 } N=3
ผลผลิต − การนับคู่ผลรวมคู่ − 6 การนับคู่ผลรวมคี่ − 0
คำอธิบาย − คู่ผลิตภัณฑ์ที่ถูกต้องคือ −
Arr[0] & Arr[1] → (2,2) Arr[1] & Arr[0] → (2,2) count=2 Arr[1] & Arr[2] → (2,2) Arr[2] & Arr[1] → (2,2) count=2 Arr[2] & Arr[3] → (2,2) Arr[3] & Arr[2] → (2,2) count=2 Total=6 No odd sum as all elements are even.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้อาร์เรย์จำนวนเต็ม arr[] ที่เริ่มต้นด้วยตัวเลขสุ่ม
-
ใช้ตัวแปร n ซึ่งเก็บความยาวของ Arr[].
-
ฟังก์ชัน countPairs(int arr[], int n) รับอาร์เรย์ ความยาวเป็นอินพุต และพิมพ์จำนวนคู่ด้วยผลรวมคู่และคี่
-
Traverse array ใช้ two for loops สำหรับแต่ละองค์ประกอบของคู่
-
วงนอกจาก 0<=i
-
ตรวจสอบว่า arr[i]+arr[j]%2==0. เพิ่มการนับ 1 สำหรับการนับคู่ผลรวมคู่โดย 2 เป็น arr[i],arr[j] และ arr[j],arr[i] จะเป็นสองคู่
-
หากเงื่อนไขข้างต้นเป็นเท็จ ให้นับ 2 สำหรับคู่ผลรวมคี่ 2
-
เมื่อสิ้นสุดลูปทั้งหมด นับ 1 จะมีจำนวนคู่ทั้งหมดที่มีผลรวมเป็นคู่ และนับ 2 จะมีจำนวนคู่ทั้งหมดที่มีผลรวมเป็นคี่
-
พิมพ์จำนวนนับ 1 และนับ 2 เป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void countPairs(int arr[], int n){
int count1=0; //even sum pairs
int count2=0; //odd sum pairs
int sum=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
sum=arr[i]+arr[j];
if(sum%2==0) //sum is even
{ count1+=2; } //(a,b) and (b,a) as two pairs
else
{ count2+=2; }
}
}
cout<<"Even Sum pairs: "<<count1;
cout<<endl<<"Odd Sum pairs: "<<count2;
}
int main(){
int arr[] = { 1,2,3,2 };
int n = sizeof(arr) / sizeof(int);
countPairs(arr, n);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Even Sum pairs: 4 Odd Sum pairs: 8
