ในปัญหานี้ เราได้รับอาร์เรย์ของ N จำนวนเต็มที่แทนความยาวของ n ไม้ งานของเราคือพิมพ์จำนวนสี่เหลี่ยมผืนผ้าและสี่เหลี่ยมจัตุรัสที่สามารถสร้างได้จากไม้ที่มีความยาวที่กำหนด
มาดูตัวอย่างเพื่อเข้าใจปัญหา:
Input - array = {5, 5, 7, 7, 1, 4}
Output - 1
Explanation - สี่เหลี่ยมผืนผ้าที่มีด้าน 5 5 7 7
เพื่อแก้ปัญหานี้ เราจะต้องตรวจสอบว่าสี่เหลี่ยมผืนผ้าและสี่เหลี่ยมจัตุรัสเป็นไปได้หรือไม่
ตอนนี้ สำหรับการสร้างสี่เหลี่ยมจัตุรัสหรือสี่เหลี่ยมผืนผ้า ควรมีไม้สอง根ที่มีความยาวเท่ากัน 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
