Hãy xem xét chúng ta có một mảng các số nguyên, đó là mảng mã hóa. Giả sử mảng là A = [10, 14, 12, 13, 11], mảng gốc là B = [5, 1, 3, 2, 4], chúng ta có thể thấy rằng mỗi phần tử tại chỉ số I của A tuân theo quy tắc này: A[i] = tổng của tất cả các phần tử tại vị trí j trong B[j], với I ≠ j. Nhiệm vụ của chúng ta là tìm mảng gốc từ mảng đã mã hóa.
Nhiệm vụ dựa trên quan sát số học. Giả sử mảng kích thước 4, mảng gốc B có bốn phần tử B = [a, b, c, d], vậy A sẽ như A[b+c+d, a+c+d, a+b+d, a+b+c], nếu cộng tất cả các phần tử của B, ta được tổng = b+c+d+a+c+d+a+b+d+a+b+c = 3*(a+b+c+d). Vậy tổng các phần tử của B sẽ là tổng/3, bây giờ nếu nhìn các phần tử của B sẽ là [tổng – A[0], tổng – A[1], tổng – A[2], tổng – A[3]]
Ví dụ
#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); }
Kết quả
5 1 3 2 4