นับคู่ในอาร์เรย์ที่เรียงลำดับซึ่งมีผลรวมน้อยกว่า x ใน C++

เราได้รับอาร์เรย์ที่เรียงลำดับขององค์ประกอบประเภทจำนวนเต็มและตัวแปรจำนวนเต็ม x และงานคือการสร้างคู่จากอาร์เรย์ที่กำหนดและคำนวณผลรวมขององค์ประกอบในคู่และตรวจสอบว่าผลรวมที่คำนวณได้น้อยกว่า x หรือไม่

ป้อนข้อมูล − int arr[] ={2, 7, 1, 0, 8}, int x =8

ผลผลิต − การนับคู่ในอาร์เรย์ที่เรียงลำดับซึ่งมีผลรวมน้อยกว่า x คือ − 4

คำอธิบาย − คู่ที่สามารถสร้างได้จากอาร์เรย์ที่กำหนด ได้แก่ (2, 7) =9(มากกว่า x), (2, 1) =3(น้อยกว่า x), (2, 0) =2(น้อยกว่า x ), (2, 8) =10(มากกว่า x), (7, 1) =8(เท่ากับ x), (7, 0) =7(น้อยกว่า x), (7, 8) =15(มากกว่า มากกว่า x), (1, 0) =1(น้อยกว่า x), (1, 8) =8(เท่ากับ x), (0, 8) =8(เท่ากับ x) ดังนั้นคู่ที่มีผลรวมน้อยกว่า x คือ (4, 0) และ (2, 2) ดังนั้น จำนวนคู่ที่มีผลรวมน้อยกว่า x คือ 4

ป้อนข้อมูล − int arr[] ={2, 4, 6, 8}, int x =10

ผลผลิต − การนับคู่ในอาร์เรย์ที่เรียงลำดับซึ่งผลรวมน้อยกว่า x คือ − 2

คำอธิบาย − คู่ที่สามารถสร้างได้จากอาร์เรย์ที่กำหนด ได้แก่ (2, 4) =6(น้อยกว่า x), (2, 6) =8(น้อยกว่า x), (2, 8) =10(เท่ากับ x ), (4, 6) =10(เท่ากับ x), (4, 8) =12(มากกว่า x), (6, 8) =14(มากกว่า x) ดังนั้น การนับคู่ที่มีผลรวมน้อยกว่า x คือ 2

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

อาจมีหลายวิธีในการแก้ปัญหาที่กำหนด เช่น แนวทางไร้เดียงสาและแนวทางที่มีประสิทธิภาพ มาดูแนวทางไร้เดียงสากันก่อน .

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

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

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

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

• ภายในลูปคำนวณผลรวมเป็น arr[i] + arr[j] และตรวจสอบ IF sum

• คืนจำนวน

• พิมพ์ผล

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

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

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

• ตั้งค่า arr_0 เป็น 0 และ arr_1 เป็น size-1

• เริ่มวนซ้ำ FOR จาก arr_0 ถึง arr_1

• ภายในลูป ให้ตรวจสอบ IF arr[arr_0] + arr[arr_1]

• คืนจำนวน

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

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

#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
   int count = 0;
   int sum = 0;
   for(int i = 0 ;i <size ; i++){
      for(int j = i+1; j<size; j++){
         sum = arr[i] + arr[j];
         if(sum < x){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {2, 7, 1, 0, 8};
   int size = sizeof(arr) / sizeof(arr[0]);
   int x = 8;
   cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of pairs in a sorted array whose sum is less than x are: 4

ตัวอย่าง (แนวทางที่มีประสิทธิภาพ)

#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
   int arr_0 = 0;
   int arr_1 = size-1;
   int count = 0;
   while(arr_0 < arr_1){
      if (arr[arr_0] + arr[arr_1] < x){
         count = count + (arr_1 - arr_0);
         arr_0++;
      }
      else{
         arr_1--;
      }
   }
   return count;
}
int main(){
   int arr[] = {2, 7, 1, 0, 8};
   int size = sizeof(arr) / sizeof(arr[0]);
   int x = 8;
   cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of pairs in a sorted array whose sum is less than x are: 4