เราได้รับอาร์เรย์ขององค์ประกอบจำนวนเต็มและงานคือการสร้างคู่จากอาร์เรย์ที่กำหนดและคำนวณผลรวมขององค์ประกอบในคู่และตรวจสอบว่าผลรวมที่กำหนดหาร 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 ลงตัว
เริ่มลูป FOR จาก i = 0 ถึงขนาดของอาร์เรย์
ภายในลูป เริ่มลูป FOR อีกอันจาก j = i + 1 ถึงขนาดของอาร์เรย์
ภายในลูป คำนวณผลรวมเป็น arr[i] + arr[j] และตรวจสอบ IF sum % k == 0 แล้วเพิ่ม count ขึ้น 1
คืนค่า count
พิมพ์ผลลัพธ์
วิธีที่มีประสิทธิภาพ
รับอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์และส่งข้อมูลไปยังฟังก์ชัน
ประกาศตัวแปรชั่วคราว count เพื่อเก็บจำนวนคู่ที่ผลรวมหาร k ลงตัว
สร้างอาร์เรย์ขนาด k เนื่องจากเราต้องตรวจสอบการหารลงตัวด้วย k
ภายในลูป ตั้ง temp เป็น arr[i] % k และ pre increment อาร์เรย์เป็น ++check[temp]
ตั้ง count เป็น new_arr[0] * (new_arr[0] - 1)/2
เริ่มลูป FOR เป็น 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
พิมพ์ผลลัพธ์
เริ่มลูป FOR จาก i = 0 ถึงขนาดของอาร์เรย์
ตัวอย่าง (วิธีเรียบง่าย)
#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
