จำนวนองค์ประกอบขั้นต่ำที่ควรลบออกเพื่อให้อาร์เรย์ใช้งานได้ดีโดยใช้ C ++

คำชี้แจงปัญหา

ด้วยอาร์เรย์ "arr" ภารกิจคือการค้นหาจำนวนองค์ประกอบขั้นต่ำที่จะลบออกเพื่อให้อาร์เรย์ทำงานได้ดี

ลำดับ a1, a2, a3 . .an เรียกว่า good ถ้าสำหรับแต่ละองค์ประกอบ a[i] มีองค์ประกอบ a[j] (i ไม่เท่ากับ j) ซึ่ง a[i] + a[j] เป็นกำลังสอง

arr1[] ={1, 1, 7, 1, 5}

ในอาร์เรย์ด้านบนถ้าเราลบองค์ประกอบ '5' อาร์เรย์จะกลายเป็นอาร์เรย์ที่ดี หลังจากนี้คู่ของ arr[i] + arr[j] จะเป็นกำลังสอง −

arr[0] + arr[1] =(1 + 1) =2 ซึ่งกำลังสอง
arr[0] + arr[2] =(1 + 7) =8 ซึ่งเป็นกำลังสอง

อัลกอริทึม

<ก่อน>1. เราต้องลบเฉพาะ a[i] ซึ่งไม่มี a[j] ที่ a[i] + a[i] เป็นกำลัง 2.2 สำหรับแต่ละค่า ให้ค้นหาจำนวนที่เกิดขึ้นในอาร์เรย์3 ตรวจสอบว่า a[i] ไม่มีคู่ a[j]

ตัวอย่าง

#include #include 
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้เนมสเปซ std;int minDeleteRequred(int *arr, int n){ map ความถี่; สำหรับ (int i =0; i  1 || (frequency[pair] ==1 &&pair !=arr[i]))) { doNotRemove =true; หยุดพัก; } } if (!doNotRemove) { ++delCnt; } } return delCnt;}int main(){ int arr[] ={1, 1, 7, 1, 5}; cout <<"องค์ประกอบขั้นต่ำที่จะลบ =" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 องค์ประกอบขั้นต่ำที่จะลบ =1