C++에서 합이 x보다 작은 정렬된 배열의 쌍 개수

<시간/>

정수형 원소의 정렬된 배열과 정수 변수 x가 주어지고 주어진 배열에서 쌍을 형성하고 쌍에 있는 원소의 합을 계산하고 계산된 합계가 x보다 작은지 여부를 확인하는 것이 작업입니다.

입력 - 정수 arr[] ={2, 7, 1, 0, 8}, 정수 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입니다.

입력 - 정수 arr[] ={2, 4, 6, 8}, 정수 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보다 작은 쌍의 개수를 저장하기 위해 임시 변수 개수를 선언합니다.
배열의 크기까지 i에서 0까지 FOR 루프 시작
루프 내에서 배열의 크기까지 j에서 i + 1까지 FOR 또 다른 루프를 시작합니다.
루프 내에서 합계를 arr[i] + arr[j]로 계산하고 IF sum
개수 반환
결과를 인쇄합니다.

효율적인 접근

정수 요소의 배열을 입력하고 배열의 크기를 계산하고 데이터를 함수에 전달
합이 x보다 작은 쌍의 개수를 저장하기 위해 임시 변수 개수를 선언합니다.
arr_0을 0으로 설정하고 arr_1을 size-1로 설정
arr_0에서 arr_1까지 FOR 루프 시작
루프 내부에서 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