ค้นหาจำนวนเต็ม X ซึ่งเป็นตัวหารทั้งหมด ยกเว้นองค์ประกอบเดียวในอาร์เรย์ใน C++

แนวคิด

สำหรับอาร์เรย์ของจำนวนเต็มที่กำหนด ภารกิจของเราคือกำหนดจำนวนเต็ม B ซึ่งเป็นตัวหารทั้งหมด ยกเว้นองค์ประกอบเดียวในอาร์เรย์ที่กำหนด

ควรสังเกตว่า GCD ขององค์ประกอบทั้งหมดไม่ใช่ 1

ป้อนข้อมูล

arr[] = {8, 16, 4, 24}

ผลผลิต

8
8 is the divisor of all except 4.

ป้อนข้อมูล

arr[] = {50, 15, 40, 41}

ผลผลิต

5
5 is the divisor of all except 41.

วิธีการ

เราสร้างอาร์เรย์นำหน้า A เพื่อให้ตำแหน่งหรือดัชนี i มี GCD ขององค์ประกอบทั้งหมดตั้งแต่ 1 ถึง i ในทำนองเดียวกัน ให้สร้างอาร์เรย์ต่อท้าย C เพื่อให้ดัชนี i มี GCD ขององค์ประกอบทั้งหมดตั้งแต่ i ถึง n-1 (ดัชนีสุดท้าย) จะเห็นได้ว่าหาก GCD ของ A[i-1] และ C[i+1] ไม่ใช่ตัวหารขององค์ประกอบที่ i แสดงว่าเป็นคำตอบที่ต้องการ

ตัวอย่าง

// C++ program to find the divisor of all
// except for exactly one element in an array.
#include <bits/stdc++.h>
using namespace std;
// Shows function that returns the divisor of all
// except for exactly one element in an array.
int getDivisor1(int a1[], int n1){
   // If there's only one element in the array
   if (n1 == 1)
      return (a1[0] + 1);
   int A[n1], C[n1];
   // Now creating prefix array of GCD
   A[0] = a1[0];
   for (int i = 1; i < n1; i++)
      A[i] = __gcd(a1[i], A[i - 1]);
   // Now creating suffix array of GCD
   C[n1-1] = a1[n1-1];
   for (int i = n1 - 2; i >= 0; i--)
      C[i] = __gcd(A[i + 1], a1[i]);
   // Used to iterate through the array
   for (int i = 0; i <= n1; i++) {
      // Shows variable to store the divisor
   int cur1;
   // now getting the divisor
   if (i == 0)
      cur1 = C[i + 1];
   else if (i == n1 - 1)
      cur1 = A[i - 1];
   else
      cur1 = __gcd(A[i - 1], C[i + 1]);
   // Used to check if it is not a divisor of a[i]
   if (a1[i] % cur1 != 0)
      return cur1;
   }
   return 0;
}
// Driver code
int main(){
   int a1[] = { 50,15,40,41 };
   int n1 = sizeof(a1) / sizeof(a1[0]);
   cout << getDivisor1(a1, n1);
   return 0;
}

ผลลัพธ์

5