通过重复减法使所有元素相同后，求最大数组和-yiteyi-C++库

给定一系列 N 元素，求出所有元素的最大可能和，使所有元素相等。唯一允许的操作是选择任意两个元素，并用两者的绝对差值替换其中较大的元素。例如：

null

Input : 9 12 3 6 Output : 12Explanation :9 12 3 6replace a₂ = 12 with a₂-a₄ = 12 - 6 => 6i.e, 9 6 3 6replace a₄ = 6 with a₄-a₃ = 6 - 3 => 3i.e, 9 6 3 3replace a₁ = 9 with a₁-a₂ = 9 - 6 => 3i.e, 3 6 3 3replace a₂ = 6 with a₂-a₄ = 6 - 3 => 3i,e. 3 3 3 3Now, at this point we have all the elements equal, hence we can return our answer from here.Input : 4 8 6 10Output : 8Explanation :Resultant array formed will be:4 8 6 10replace a₄ = 10 with a₄-a₁ = 10 - 4 => 6i.e, 4 8 6 6replace a₃ = 6 with a₃-a₁ = 6 - 4 => 2i.e, 4 8 2 6replace a₂ = 8 with a₂-a₄ = 8 - 6 => 2i.e, 4 2 2 6replace a₄ = 6 with a₄-a₁ = 6 - 4 => 2i,e. 4 2 2 2replace a₁ = 4 with a₁-a₂ = 4 - 2 => 2i,e. 2 2 2 2Now, at this point we have all the elements equal, hence we can return our answer from here.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

通过分析给定的操作，

    a_i = a_i - a_j          where a_i > a_j

我们发现这与通过欧几里德算法作为：

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

而且，重排的顺序也无关紧要，我们可以取任意两个元素，用两个元素的绝对差值替换较大的值，并在它们之间重复，直到差值为零（两个元素相同）。也就是说，去掉任意两个数字的GCD。这样做的原因是，GCD是关联的和可交换的。所以我们的想法是一次获取所有元素的GCD，然后用这个结果替换所有元素。

C++

                         // Maximum possible sum of array after repeated                       
                         // subtraction operation.                       
                         #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;                       
                         }                       
           
                         // This function basically calls findMaxSumUtil()                       
                         // to find GCD of all array elements, then it returns                       
                         // GCD * (Size of array)                       
                         int                                     findMaxSum(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     maxElement = findMaxSumUtil(arr, n);                       
                                                 return                                     (maxElement * n);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {8, 20, 12, 36};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 cout << findMaxSum(arr, n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Maximum possible sum of array after repeated                       
                         // subtraction operation.                       
           
                         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;                       
                                                 }                       
                                   
                                                 // This function basically calls                       
                                                 // findMaxSumUtil() to find GCD of all                       
                                                 // array elements, then it returns                       
                                                 // GCD * (Size of array)                       
                                                 static                                     int                                     findMaxSum(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     maxElement = findMaxSumUtil(arr, n);                       
                                                 return                                     (maxElement * n);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args) {                       
                                   
                                                 int                                     arr[] = {                                     8                                     ,                                     20                                     ,                                     12                                     ,                                     36                                     };                       
                                                 int                                     n = arr.length;                       
                                   
                                                 System.out.println(findMaxSum(arr, n));                       
                                                 }                       
                         }                       
           
                         //This code is contributed by vt_m.                       

Python3

                         # Maximum possible sum of array after                       
                         # repeated subtraction operation.                       
           
                         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                       
           
                         # This function basically calls                       
                         # findMaxSumUtil() to find GCD of                       
                         # all array elements, then it returns                       
                         # GCD * (Size of array)                       
                         def                                     findMaxSum(arr, n):                       
           
                                                 maxElement                                     =                                     findMaxSumUtil(arr, n)                       
                                                 return                                     (maxElement                                     *                                     n)                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     8                                     ,                                     20                                     ,                                     12                                     ,                                     36                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (findMaxSum(arr, n))                       
           
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# Code for Maximum possible sum of array                       
                         // after repeated subtraction operation.                       
                         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;                       
                                                 }                       
                                   
                                                 // This function basically calls                       
                                                 // findMaxSumUtil() to find GCD of all                       
                                                 // array elements, then it returns                       
                                                 // GCD * (Size of array)                       
                                                 static                                     int                                     findMaxSum(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 int                                     maxElement = findMaxSumUtil(arr, n);                       
                                                 return                                     (maxElement * n);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main () {                       
                                   
                                                 int                                     []arr = {8, 20, 12, 36};                       
                                                 int                                     n = arr.Length;                       
                                   
                                                 Console.WriteLine(findMaxSum(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP code to find Maximum possible                       
                         // sum of array after repeated                       
                         // subtraction operation.                       
           
                         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                                     ;                       
                         }                       
           
                         // This function basically                       
                         // calls findMaxSumUtil()                       
                         // to find GCD of all array                       
                         // elements, then it returns                       
                         // GCD * (Size of array)                       
                         function                                     findMaxSum(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $maxElement                                     = findMaxSumUtil(                                     $arr                                     ,                                     $n                                     );                       
                                                 return                                     (                                     $maxElement                                     *                                     $n                                     );                       
                         }                       
           
                                                 // Driver Code                       
                                                 $arr                                     =                                     array                                     (8, 20, 12, 36);                       
                                                 $n                                     =                                     count                                     (                                     $arr                                     );                       
                                                 echo                                     findMaxSum(                                     $arr                                     ,                                     $n                                     ) ;                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript Code for Maximum possible sum of array                       
                                                 // after repeated subtraction operation.                       
                                   
                                                 function                                     GCD(a, b)                       
                                                 {                       
                                                 if                                     (b == 0)                       
                                                 return                                     a;                       
                                                 return                                     GCD(b, a % b);                       
                                                 }                       
                                   
                                                 function                                     findMaxSumUtil(arr, n)                       
                                                 {                       
                                                 let finalGCD = arr[0];                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 finalGCD = GCD(arr[i], finalGCD);                       
                                   
                                                 return                                     finalGCD;                       
                                                 }                       
                                   
                                                 // This function basically calls                       
                                                 // findMaxSumUtil() to find GCD of all                       
                                                 // array elements, then it returns                       
                                                 // GCD * (Size of array)                       
                                                 function                                     findMaxSum(arr, n)                       
                                                 {                       
                                                 let maxElement = findMaxSumUtil(arr, n);                       
                                                 return                                     (maxElement * n);                       
                                                 }                       
                                   
                                                 let arr = [8, 20, 12, 36];                       
                                                 let n = arr.length;                       
           
                                                 document.write(findMaxSum(arr, n));                       
                                   
                         </script>                       

输出：

本文由舒巴姆·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章