C++에서 주어진 요소 집합으로 가능한 사각형 및 사각형 수

이 문제에서는 n개의 막대기 길이를 나타내는 N개의 정수 배열이 제공됩니다. 우리의 임무는 주어진 길이의 막대기로 만들 수 있는 직사각형과 정사각형의 개수를 인쇄하는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 배열 ={5, 5, 7, 7, 1, 4}

출력 − 1

설명 - 변이 5 5 7 7인 직사각형.

이 문제를 해결하려면 직사각형과 정사각형이 가능한지 여부를 확인해야 합니다.

이제 정사각형이나 직사각형을 만들려면 길이가 같은 막대 2개가 있어야 합니다. 직사각형은 2개, 정사각형은 4개입니다. 이제 배열에서 동일한 길이의 막대 쌍을 확인해야 합니다. 이 검색을 쉽게 하기 위해 배열을 정렬한 다음 쌍을 찾고 전체 쌍 수의 절반이 만들 수 있는 정사각형 또는 직사각형의 수입니다.

예시

솔루션 구현을 보여주는 프로그램,

#include <bits/stdc++.h>
using namespace std;
int countRecSqr(int sticks[], int n) {
   sort(sticks, sticks + n);
   int pairs = 0;
   for (int i = 0; i < n - 1; i++) {
      if (sticks[i]==sticks[i + 1]) {
         pairs++;
         i++;
      }
   }
   return pairs / 2;
}
int main() {
   int sticks[] = { 2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9 };
   int n = sizeof(sticks) / sizeof(sticks[0]);
   cout<<"The total number of squares or rectangles that can be created is ";
   cout<<countRecSqr(sticks, n);
   return 0;
}

출력

The total number of squares or rectangles that can be created is 3