Encuentre la array original de una array cifrada dada de tamaño n. La array cifrada se obtiene reemplazando cada elemento de la array original por la suma de los elementos restantes de la array.
Ejemplos:
Input : arr[] = {10, 14, 12, 13, 11}
Output : {5, 1, 3, 2, 4}
Original array {5, 1, 3, 2, 4}
Encrypted array is obtained as:
= {1+3+2+4, 5+3+2+4, 5+1+2+4, 5+1+3+4, 5+1+3+2}
= {10, 14, 12, 13, 11}
Each element of original array is replaced by the
sum of the remaining array elements.
Input : arr[] = {95, 107, 103, 88, 110, 87}
Output : {23, 11, 15, 30, 8, 31}
El enfoque se basa puramente en observaciones aritméticas que se ilustran a continuación:
Let n = 4, and
the original array be ori[] = {a, b, c, d}
encrypted array is given as:
arr[] = {b+c+d, a+c+d, a+b+d, a+b+c}
Elements of encrypted array are :
arr[0] = (b+c+d), arr[1] = (a+c+d),
arr[2] = (a+b+d), arr[3] = (a+b+c)
add up all the elements
sum = arr[0] + arr[1] + arr[2] + arr[3]
= (b+c+d) + (a+c+d) + (a+b+d) + (a+b+c)
= 3(a+b+c+d)
Sum of elements of ori[] = sum / n-1
= sum/3
= (a+b+c+d)
Thus, for a given encrypted array arr[] of size n, the sum of
the elements of the original array ori[] can be calculated as:
sum = (arr[0]+arr[1]+....+arr[n-1]) / (n-1)
Then, elements of ori[] are calculated as:
ori[0] = sum - arr[0]
ori[1] = sum - arr[1]
.
.
ori[n-1] = sum - arr[n-1]
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ implementation to find original array
// from the encrypted array
#include <bits/stdc++.h>
using namespace std;
// Finds and prints the elements of the original
// array
void findAndPrintOriginalArray(int arr[], int n)
{
// total sum of elements
// of encrypted array
int arr_sum = 0;
for (int i=0; i<n; i++)
arr_sum += arr[i];
// total sum of elements
// of original array
arr_sum = arr_sum/(n-1);
// calculating and displaying
// elements of original array
for (int i=0; i<n; i++)
cout << (arr_sum - arr[i]) << " ";
}
// Driver program to test above
int main()
{
int arr[] = {10, 14, 12, 13, 11};
int n = sizeof(arr) / sizeof(arr[0]);
findAndPrintOriginalArray(arr, n);
return 0;
}
Java
import java.util.*;
class GFG {
// Finds and prints the elements of the original
// array
static void findAndPrintOriginalArray(int arr[], int n)
{
// total sum of elements
// of encrypted array
int arr_sum = 0;
for (int i = 0; i < n; i++) {
arr_sum += arr[i];
}
// total sum of elements
// of original array
arr_sum = arr_sum / (n - 1);
// calculating and displaying
// elements of original array
for (int i = 0; i < n; i++) {
System.out.print(arr_sum - arr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 10, 14, 12, 13, 11 };
int n = arr.length;
findAndPrintOriginalArray(arr, n);
}
}
// This code is contributed by rj13to.
Python 3
# Python 3 implementation to find # original array from the encrypted # array # Finds and prints the elements of # the original array def findAndPrintOriginalArray(arr, n): # total sum of elements # of encrypted array arr_sum = 0 for i in range(0, n): arr_sum += arr[i] # total sum of elements # of original array arr_sum = int(arr_sum / (n - 1)) # calculating and displaying # elements of original array for i in range(0, n): print((arr_sum - arr[i]), end = " ") # Driver program to test above arr = [10, 14, 12, 13, 11] n = len(arr) findAndPrintOriginalArray(arr, n) # This code is contributed By Smitha
C#
// C# program to find original
// array from the encrypted array
using System;
class GFG {
// Finds and prints the elements
// of the original array
static void findAndPrintOriginalArray(int []arr,
int n)
{
// total sum of elements
// of encrypted array
int arr_sum = 0;
for (int i = 0; i < n; i++)
arr_sum += arr[i];
// total sum of elements
// of original array
arr_sum = arr_sum / (n - 1);
// calculating and displaying
// elements of original array
for (int i = 0; i < n; i++)
Console.Write(arr_sum - arr[i] + " ");
}
// Driver Code
public static void Main (String[] args)
{
int []arr = {10, 14, 12, 13, 11};
int n =arr.Length;
findAndPrintOriginalArray(arr, n);
}
}
// This code is contributed by parashar...
PHP
<?php
// PHP implementation to find
// original array from the
// encrypted array
// Finds and prints the elements
// of the original array
function findAndPrintOriginalArray($arr, $n)
{
// total sum of elements
// of encrypted array
$arr_sum = 0;
for ( $i = 0; $i < $n; $i++)
$arr_sum += $arr[$i];
// total sum of elements
// of original array
$arr_sum = $arr_sum / ($n - 1);
// calculating and displaying
// elements of original array
for ( $i = 0; $i < $n; $i++)
echo $arr_sum - $arr[$i] , " ";
}
// Driver Code
$arr = array(10, 14, 12, 13, 11);
$n = count($arr);
findAndPrintOriginalArray($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find original
// array from the encrypted array
// Finds and prints the elements
// of the original array
function findAndPrintOriginalArray(arr, n)
{
// total sum of elements
// of encrypted array
let arr_sum = 0;
for (let i = 0; i < n; i++)
arr_sum += arr[i];
// total sum of elements
// of original array
arr_sum = parseInt(arr_sum / (n - 1), 10);
// calculating and displaying
// elements of original array
for (let i = 0; i < n; i++)
document.write(arr_sum - arr[i] + " ");
}
let arr = [10, 14, 12, 13, 11];
let n =arr.length;
findAndPrintOriginalArray(arr, n);
// This code is contributed by rameshtravel07.
</script>
Producción
5 1 3 2 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA