ลองพิจารณาว่าเรามีอาร์เรย์ของจำนวนเต็ม อาร์เรย์นั้นคืออาร์เรย์ที่เข้ารหัส (Encrypted Array) สมมติอาร์เรย์คือ A = [10, 14, 12, 13, 11] อาร์เรย์ต้นฉบับคือ B = [5, 1, 3, 2, 4] เราสามารถเห็นได้ว่าสมาชิกแต่ละตัวที่ดัชนี i ของ A ปฏิบัติตามกฎนี้: A[i] = ผลรวมของสมาชิกทั้งหมดที่ตำแหน่ง j ใน B[j] โดยที่ i ≠ j ภารกิจของเราคือหาอาร์เรย์ต้นฉบับจากอาร์เรย์ที่เข้ารหัส
งานนี้ขึ้นอยู่กับการสังเกตทางคณิตศาสตร์ สมมติอาร์เรย์ขนาด 4 อาร์เรย์ต้นฉบับ B มี 4 สมาชิก B = [a, b, c, d] ดังนั้น A จะเป็น A[b+c+d, a+c+d, a+b+d, a+b+c] ถ้าเราบวกสมาชิกทั้งหมดของ B เราจะได้ sum = b+c+d+a+c+d+a+b+d+a+b+c = 3*(a+b+c+d) ดังนั้นผลรวมของสมาชิกของ B จะเป็น sum/3 ตอนนี้ถ้าเราดูสมาชิกของ B จะเป็น [sum - A[0], sum - A[1], sum - A[2], sum - A[3]]
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
void showOrigianlArray(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
sum = sum / (n - 1);
for (int i = 0; i < n; i++)
cout << (sum - arr[i]) << " ";
}
int main() {
int arr[] = {10, 14, 12, 13, 11};
int n = sizeof(arr) / sizeof(arr[0]);
showOrigianlArray(arr, n);
}
ผลลัพธ์
5 1 3 2 4
