ค้นหาว่าอาร์เรย์มีองค์ประกอบที่มีค่าเท่ากับครึ่งหนึ่งของผลรวมอาร์เรย์ใน C++ . หรือไม่

ในปัญหานี้ เราได้รับอาร์เรย์ arr ของค่าที่ไม่ซ้ำกันที่จัดเรียงไว้ งานของเราคือ ค้นหาว่าอาร์เรย์มีองค์ประกอบที่มีค่าเท่ากับครึ่งหนึ่งของผลรวมอาร์เรย์หรือไม่ .

คำอธิบายปัญหา: สำหรับอาร์เรย์ arr[] เราจำเป็นต้องค้นหาองค์ประกอบ x ในอาร์เรย์เพื่อให้ผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์เท่ากับ 2*X

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: arr[] ={2, 4, 5, 6, 7}

ผลลัพธ์: ไม่

คำอธิบาย:

ผลรวม =2 + 4 + 5 + 6 + 7 =24

ไม่พบองค์ประกอบ

แนวทางแก้ไข:

ในการแก้ปัญหา เราเพียงแค่ต้องค้นหาองค์ประกอบที่เป็นครึ่งหนึ่งของผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์

อัลกอริทึม:

ขั้นตอนที่ 1: หาผลรวมของอิลิเมนต์ทั้งหมดของอาร์เรย์

ขั้นตอนที่ 2: ถ้าผลรวมเป็นเลขคี่ ให้คืนค่า -1

ขั้นตอนที่ 3: ถ้าผลรวมมีค่าเท่ากัน ให้หาองค์ประกอบ x ที่ x*2 =ผลรวม

ขั้นตอนที่ 4: หากพบองค์ประกอบ ให้คืนค่า 1
ขั้นตอนที่ 5: หากไม่พบองค์ประกอบส่งคืน -1.

สำหรับการค้นหาองค์ประกอบ เราสามารถใช้ อัลกอริทึมการค้นหาแบบไบนารี ตามที่จัดเรียงไว้

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;

int checkForElement(int array[], int n) {

   int arrSum = 0;
   for (int i = 0; i < n; i++)
      arrSum += array[i];

   if (arrSum % 2)
   return -1;

   int start = 0;
   int end = n - 1;
   while (start <= end)
   {
      int mid = start + (end - start) / 2;
      if ( ( 2 * array[mid] ) == arrSum)
         return array[mid];      
      else if (( 2 * array[mid] ) > arrSum)
         end = mid - 1;      
      else
         start = mid + 1;
   }

   return -1;
}

int main() {

   int array[] = { 4, 5, 6, 7, 9 };
   int n = sizeof(array) / sizeof(array[0]);
   int x = checkForElement(array, n);
   if(x != -1)
    cout<<"Element found, value is "<<x;
   else
    cout<<"Element not found!";
   return 0;
}

ผลลัพธ์ -

Element not found!