Given two integers N and X which denotes the size of an array arr[] and the initial value of all the array elements respectively, the task is to find the maximum sum possible from the given array after performing the following operation any number of times.
Choose any valid index i for which arr[i] = arr[i + 1] and update arr[i] = arr[i] + arr[i + 1] and arr[i + 1] = X.
Examples:
Input: N = 3, X = 5
Output: 35
Explanation:
Initially arr[] = [5, 5, 5]
Performing the given operation on i = 1, arr[] = [10, 5, 5]
Performing the given operation on i = 2, arr[] = [10, 10, 5]
Performing the given operation on i = 1, arr[] = [20, 5, 5]
Performing the given operation on i = 2, arr[] = [20, 10, 5]
No adjacent equal elements are present in the array.
Therefore, the maximum possible sum from the array is 35.Input: N = 2, X = 3
Output: 9
Explanation:
Initially arr[] = [3, 3]
Performing the given operation on i = 1, arr[] = [6, 3]
No adjacent equal elements are present in the array.
Therefore, the maximum possible sum from the array is 9.
Naive Approach: The idea is to perform the given operation on every valid index in the initial array and find the maximum possible sum form all possible array rearrangements.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using the following observation:
- From the aforementioned examples, it can be observed that the value of the element at index i in the final array is given by:
X * 2(N – i – 1)
- Therefore, the sum of the final array will be equal to the sum of the series X * 2(N – i – 1) for every valid index i.
- The sum of the above series is given by:
Sum of the series = X * (2N – 1)
Therefore, simply print X * (2N – 1) as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std; // Function to calculate x ^ yint power(int x, int y){ int temp; // Base Case if (y == 0) return 1; // Find the value in temp temp = power(x, y / 2); // If y is even if (y % 2 == 0) return temp * temp; else return x * temp * temp;} // Function that find the maximum// possible sum of the arrayvoid maximumPossibleSum(int N, int X){ // Print the result using // the formula cout << (X * (power(2, N) - 1)) << endl;} // Driver codeint main(){ int N = 3, X = 5; // Function call maximumPossibleSum(N, X);}// This code is contributed by rutvik_56 |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to calculate x ^ y static int power(int x, int y) { int temp; // Base Case if (y == 0) return 1; // Find the value in temp temp = power(x, y / 2); // If y is even if (y % 2 == 0) return temp * temp; else return x * temp * temp; } // Function that find the maximum // possible sum of the array public static void maximumPossibleSum(int N, int X) { // Print the result using // the formula System.out.println( X * (power(2, N) - 1)); } // Driver Code public static void main(String[] args) { int N = 3, X = 5; // Function Call maximumPossibleSum(N, X); }} |
Python3
# Python3 program for the above approach # Function to calculate x ^ y def power(x, y): # Base Case if(y == 0): return 1 # Find the value in temp temp = power(x, y // 2) # If y is even if(y % 2 == 0): return temp * temp else: return x * temp * temp# Function that find the maximum# possible sum of the arraydef maximumPossibleSum(N, X): # Print the result using # the formula print(X * (power(2, N) - 1))# Driver CodeN = 3X = 5# Function callmaximumPossibleSum(N, X)# This code is contributed by Shivam Singh |
C#
// C# program for // the above approachusing System;class GFG{// Function to calculate x ^ ystatic int power(int x, int y){ int temp; // Base Case if (y == 0) return 1; // Find the value in temp temp = power(x, y / 2); // If y is even if (y % 2 == 0) return temp * temp; else return x * temp * temp;}// Function that find the maximum// possible sum of the arraypublic static void maximumPossibleSum(int N, int X){ // Print the result using // the formula Console.WriteLine(X * (power(2, N) - 1));}// Driver Codepublic static void Main(String[] args){ int N = 3, X = 5; // Function Call maximumPossibleSum(N, X);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach // Function to calculate x ^ y function power(x , y) { var temp; // Base Case if (y == 0) return 1; // Find the value in temp temp = power(x, parseInt(y / 2)); // If y is even if (y % 2 == 0) return temp * temp; else return x * temp * temp; } // Function that find the maximum // possible sum of the array function maximumPossibleSum(N , X) { // Print the result using // the formula document.write(X * (power(2, N) - 1)); } // Driver Code var N = 3, X = 5; // Function Call maximumPossibleSum(N, X);// This code contributed by aashish1995</script> |
35
Time Complexity: O(log N), The time complexity of this code is O(log N) because the power function is called recursively with a value of y being halved at each recursive call. Therefore, the number of recursive calls required to reach the base case of y=0 is log base 2 of N.
Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
