Рубрики

Найти исходный массив из зашифрованного массива (массив сумм других элементов)

Найти исходный массив из заданного зашифрованного массива размером n. Зашифрованный массив получается путем замены каждого элемента исходного массива суммой оставшихся элементов массива.


Примеры :

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}

Подход основан исключительно на арифметических наблюдениях, которые проиллюстрированы ниже:

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]                      

Ниже приведена реализация вышеуказанных шагов.

C ++

// реализация C ++ для поиска исходного массива
// из зашифрованного массива
#include <bits/stdc++.h>

using namespace std;

  
// Находит и печатает элементы оригинала
// массив

void findAndPrintOriginalArray(int arr[], int n)

{

    // общая сумма элементов

    // зашифрованного массива

    int arr_sum = 0;

    for (int i=0; i<n; i++)

        arr_sum += arr[i];

  

    // общая сумма элементов

    // исходного массива

    arr_sum = arr_sum/(n-1);

  

    // вычисление и отображение

    // элементы исходного массива

    for (int i=0; i<n; i++)

        cout << (arr_sum - arr[i]) << " ";

}

  
// Программа драйвера для тестирования выше

int main()

{

    int arr[] = {10, 14, 12, 13, 11};

    int n = sizeof(arr) / sizeof(arr[0]);

    findAndPrintOriginalArray(arr, n);

    return 0;

}

Джава

// Java реализация для поиска оригинала
// массив из зашифрованного массива

  

class GFG

{

    // Находит и печатает элементы

    // исходного массива

    static void findAndPrintOriginalArray(int arr[], 

                                          int n)

    {

        // общая сумма элементов

        // зашифрованного массива

        int arr_sum = 0;

        for (int i = 0; i < n; i++)

            arr_sum += arr[i];

  

        // общая сумма элементов

        // исходного массива

        arr_sum = arr_sum / (n - 1);

  

        // вычисление и отображение

        // элементы исходного массива

        for (int i = 0; i < n; i++)

            System.out.print(arr_sum - arr[i] + " ");

    }

  

    // Программа драйвера для тестирования выше

    public static void main (String[] args)

    {

        int arr[] = {10, 14, 12, 13, 11};

        int n =arr.length;

        findAndPrintOriginalArray(arr, n);

    }

}

  
// Этот код предоставлен Anant Agarwal.

Python 3

# Реализация Python 3 для поиска
# оригинальный массив из зашифрованного
# массив

  
# Находит и печатает элементы
# исходный массив

def findAndPrintOriginalArray(arr, n):

  

    # общая сумма элементов

    # зашифрованного массива

    arr_sum = 0

    for i in range(0, n):

        arr_sum += arr[i]

  

    # общая сумма элементов

    # исходного массива

    arr_sum = int(arr_sum / (n - 1))

  

    # расчет и отображение

    # элементы исходного массива

    for i in range(0, n):

        print((arr_sum - arr[i]), 

                       end = " ")

  
# Программа драйвера для тестирования выше

arr = [10, 14, 12, 13, 11]

n = len(arr)

findAndPrintOriginalArray(arr, n)

  
# Этот код предоставлен Смитой

C #

// C # программа для поиска оригинала
// массив из зашифрованного массива

using System;

  

class GFG {

      

    // Находит и печатает элементы

    // исходного массива

    static void findAndPrintOriginalArray(int []arr, 

                                          int n)

    {

          

        // общая сумма элементов

        // зашифрованного массива

        int arr_sum = 0;

        for (int i = 0; i < n; i++)

            arr_sum += arr[i];

  

        // общая сумма элементов

        // исходного массива

        arr_sum = arr_sum / (n - 1);

  

        // вычисление и отображение

        // элементы исходного массива

        for (int i = 0; i < n; i++)

        Console.Write(arr_sum - arr[i] + " ");

    }

  

    // Код драйвера

    public static void Main (String[] args)

    {

        int []arr = {10, 14, 12, 13, 11};

        int n =arr.Length;

        findAndPrintOriginalArray(arr, n);

    }

}

  
// Этот код предоставлен parashar ...

PHP

<?php
// Реализация PHP для поиска
// исходный массив из
// зашифрованный массив

  
// Находит и печатает элементы
// исходного массива

function findAndPrintOriginalArray($arr, $n)

{

    // общая сумма элементов

    // зашифрованного массива

    $arr_sum = 0;

    for ( $i = 0; $i < $n; $i++)

        $arr_sum += $arr[$i];

  

    // общая сумма элементов

    // исходного массива

    $arr_sum = $arr_sum / ($n - 1);

  

    // вычисление и отображение

    // элементы исходного массива

    for ( $i = 0; $i < $n; $i++) 

        echo $arr_sum - $arr[$i] , " ";

}

  
// Код драйвера

$arr = array(10, 14, 12, 13, 11);

$n = count($arr);

findAndPrintOriginalArray($arr, $n);

  
// Этот код предоставлен anuj_67.
?>


Выход :

5 1 3 2 4

Временная сложность: O (n)

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти исходный массив из зашифрованного массива (массив сумм других элементов)

0.00 (0%) 0 votes