นับคู่ในอาร์เรย์ที่ผลรวมหารด้วย K ใน C++ . ลงตัว

เราได้รับอาร์เรย์ขององค์ประกอบประเภทจำนวนเต็ม และภารกิจคือการสร้างคู่จากอาร์เรย์ที่กำหนดและคำนวณผลรวมขององค์ประกอบในคู่และตรวจสอบว่าผลรวมที่กำหนดนั้นหารด้วย 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 จากนั้นคำนวณขนาดของอาร์เรย์แล้วส่งข้อมูลไปยังฟังก์ชัน

• ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บจำนวนคู่โดยมีผลรวมหารด้วย k ลงตัว

• เริ่มการวนซ้ำ FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์

• ภายในลูป เริ่มวนใหม่ FOR จาก j ถึง i + 1 จนถึงขนาดอาร์เรย์

• ภายในลูปคำนวณผลรวมเป็น arr[i] + arr[j] และตรวจสอบ IF sum % k ==0 แล้วเพิ่มจำนวนขึ้น 1

• คืนจำนวน

• พิมพ์ผล

แนวทางที่มีประสิทธิภาพ

• ป้อนอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์แล้วส่งข้อมูลไปยังฟังก์ชัน

• ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บจำนวนคู่โดยมีผลรวมหารด้วย k ลงตัว

• สร้างอาร์เรย์ขนาด k เนื่องจากเราต้องตรวจสอบการหารด้วย k

• เริ่มการวนซ้ำ FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์

• ภายในลูป ตั้งค่า temp เป็น arr[i] % k และเพิ่มอาร์เรย์ล่วงหน้าเป็น ++check[temp]

• ตั้งเป็น new_arr[0] * (new_arr[0] - 1)/2

• เริ่มวนซ้ำ FOR as i ถึง 1 จนถึง i <=k/2 AND i !=(k-i)

• ภายในลูป ตั้งค่า count as count + new_arr[i] * (new_arr[k - i])

• ตรวจสอบ IF k % 2 =0 แล้วตั้งค่า count เป็น count + (new_arr[k / 2] * (new_arr[k / 2] - 1) / 2)

• คืนจำนวน

• พิมพ์ผลลัพธ์

ตัวอย่าง (แนวทางไร้เดียงสา)

#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