Рубрики

Найти максимальную сумму массива после создания всех элементов одинаковыми с повторным вычитанием

Для данного массива из n элементов определите максимально возможную сумму всех элементов, чтобы все элементы были равны. Единственной допустимой операцией является выбор любых двух элементов и замена большего из них абсолютной разностью двух.

Примеры:

Input : 9 12 3 6 
Output : 12
Explanation :
9 12 3 6
replace a2 = 12 with a2-a4 = 12 - 6 => 6
i.e, 9 6 3 6

replace a4 = 6 with a4-a3 = 6 - 3 => 3
i.e, 9 6 3 3

replace a1 = 9 with a1-a2 = 9 - 6 => 3
i.e, 3 6 3 3

replace a2 = 6 with a2-a4 = 6 - 3 => 3
i,e. 3 3 3 3

Now, at this point we have all the elements equal, 
hence we can return our answer from here.


Input : 4 8 6 10
Output : 8
Explanation :
Resultant array formed will be:
4 8 6 10
replace a4 = 10 with a4-a1 = 10 - 4 => 6
i.e, 4 8 6 6

replace a3 = 6 with a3-a1 = 6 - 4 => 2
i.e, 4 8 2 6

replace a2 = 8 with a2-a4 = 8 - 6 => 2
i.e, 4 2 2 6

replace a4 = 6 with a4-a1 = 6 - 4 => 2
i,e. 4 2 2 2

replace a1 = 4 with a1-a2 = 4 - 2 => 2
i,e. 2 2 2 2

Now, at this point we have all the elements equal, 
hence we can return our answer from here.

Анализируя данную операцию, т. Е.

    ai = ai - aj          where ai > aj

Мы видим, что это похоже на поиск ГКД по евклидову алгоритму как:

   GCD(a, b) = GCD(b, a - b)

Кроме того, порядок перестановки не имеет значения, мы можем продолжить, беря любые два элемента и заменяя большее значение абсолютной разностью двух, и повторять их, пока разница не станет равной нулю [оба элемента одинаковы ]. То есть вынимаем GCD из любых двух чисел. Причиной этого является то, что GCD является ассоциативным и коммутативным.

Таким образом, идея состоит в том, чтобы взять GCD всех элементов одновременно и заменить все элементы этим результатом.

C ++

// Максимально возможная сумма массива после повторения
// операция вычитания.
#include<bits/stdc++.h>

using namespace std;

  

int GCD(int a, int b)

{

    if (b == 0)

        return a;

    return GCD(b, a % b);

}

  

int findMaxSumUtil(int arr[], int n)

{

    int finalGCD = arr[0];

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

        finalGCD = GCD(arr[i], finalGCD);

  

    return finalGCD;

}

  
// Эта функция в основном вызывает findMaxSumUtil ()
// найти GCD всех элементов массива, затем он возвращает
// GCD * (размер массива)

int findMaxSum(int arr[], int n)

{

    int maxElement = findMaxSumUtil(arr, n);

    return (maxElement * n);

}

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

int main()

{

    int arr[] = {8, 20, 12, 36};

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

    cout << findMaxSum(arr, n) << endl;

    return 0;

}

Джава

// Максимально возможная сумма массива после повторения
// операция вычитания.

  

import java.io.*;

  

class GFG {

  

    static int GCD(int a, int b)

    {

        if (b == 0)

            return a;

        return GCD(b, a % b);

    }

      

    static int findMaxSumUtil(int arr[], int n)

    {

        int finalGCD = arr[0];

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

            finalGCD = GCD(arr[i], finalGCD);

      

        return finalGCD;

    }

      

    // Эта функция в основном вызывает

    // findMaxSumUtil (), чтобы найти GCD всех

    // массив элементов, затем он возвращает

    // GCD * (размер массива)

    static int findMaxSum(int arr[], int n)

    {

        int maxElement = findMaxSumUtil(arr, n);

        return (maxElement * n);

    }

  

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

    public static void main (String[] args) {

          

        int arr[] = {8, 20, 12, 36};

        int n = arr.length;

          

        System.out.println(findMaxSum(arr, n));

    }

}

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

python3

# Максимально возможная сумма массива после
# повторная операция вычитания.

  

def GCD(a, b):

  

    if (b == 0): return a

    return GCD(b, a % b)

  

def findMaxSumUtil(arr, n):

  

    finalGCD = arr[0]

    for i in range(1, n):

        finalGCD = GCD(arr[i], finalGCD)

  

    return finalGCD

  
# Эта функция в основном вызывает
# findMaxSumUtil () для поиска GCD из
# все элементы массива, затем он возвращает
# GCD * (размер массива)

def findMaxSum(arr, n):

  

    maxElement = findMaxSumUtil(arr, n)

    return (maxElement * n)

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

arr = [8, 20, 12, 36]

n = len(arr)

print(findMaxSum(arr, n))

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

C #

// C # код для максимально возможной суммы массива
// после повторной операции вычитания.

using System;

  

class GFG {

  

    static int GCD(int a, int b)

    {

        if (b == 0)

            return a;

        return GCD(b, a % b);

    }

      

    static int findMaxSumUtil(int []arr, int n)

    {

        int finalGCD = arr[0];

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

            finalGCD = GCD(arr[i], finalGCD);

      

        return finalGCD;

    }

      

    // Эта функция в основном вызывает

    // findMaxSumUtil (), чтобы найти GCD всех

    // массив элементов, затем он возвращает

    // GCD * (размер массива)

    static int findMaxSum(int []arr, int n)

    {

        int maxElement = findMaxSumUtil(arr, n);

        return (maxElement * n);

    }

  

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

    public static void Main () {

          

        int []arr = {8, 20, 12, 36};

        int n = arr.Length;

          

        Console.WriteLine(findMaxSum(arr, n));

    }

}

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

PHP

<?php
// PHP-код для поиска максимально возможного
// сумма массива после повторения
// операция вычитания.

  

function GCD($a, $b)

{

    if ($b == 0)

        return $a;

    return GCD($b, $a % $b);

}

  

function findMaxSumUtil( $arr, $n)

{

    $finalGCD = $arr[0];

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

        $finalGCD = GCD($arr[$i], $finalGCD);

  

    return $finalGCD;

}

  
// Эта функция в основном
// вызывает findMaxSumUtil ()
// найти GCD всего массива
// элементы, затем он возвращает
// GCD * (размер массива)

function findMaxSum( $arr, $n)

{

    $maxElement = findMaxSumUtil($arr, $n);

    return ($maxElement * $n);

}

  

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

    $arr = array(8, 20, 12, 36);

    $n = count($arr);

    echo findMaxSum($arr, $n) ;

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


Выход:

 16

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

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

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

Найти максимальную сумму массива после создания всех элементов одинаковыми с повторным вычитанием

0.00 (0%) 0 votes