Given an array arr[] of size N and integer K, the task is to maximize the sum of the array by performing the following operations any number of times(possibly zero):
- Choose two indices, i and j where arr[i] must be a multiple of K.
- Make arr[i] = arr[i]/K and arr[j] = K*arr[j]
- After performing the above operations, the sum of the elements of the array must be maximum.
Examples:
Input: arr[] = {6, 6, 3}, N = 3, K = 3
Output: 57
Explanation: The optimal sequence for which sum of the array elements would be maximized is:
- Take i = 0 and j = 1, arr[0] = arr[0]/3 = 2, arr[1] = arr[1]*3 = 18, now the new array becomes, [2, 18, 3]
- Take i = 2 and j = 1, arr[2] = arr[2]/3 = 1, arr[1] = arr[1]*3 = 54, the array becomes [2, 54, 1]
Sum = 2 + 54 + 1 = 57
Input: arr[] = {1, 2, 3, 4, 5}, N = 5, K = 2
Output: 46
Explanation: The operation performed is:
Take i = 1 and j = 4, arr[1] = arr[1]/2 = 1, arr[4] = arr[4]*2 = 10. Now arr[] = {1, 1, 3, 4, 10}.
Take i = 3 and j = 4, arr[3] = arr[3]/2 = 2, arr[4] = arr[4]*2 = 20. Now arr[] = {1, 1, 3, 2, 20}.
Take i = 3 and j = 4, arr[3] = arr[3]/2 = 1, arr[4] = arr[4]*2 = 40. Now arr[] = {1, 1, 3, 1, 40}
Sum = 1 + 1+ 3 + 1 + 40 = 46.
Approach: The greedy approach is to divide all the array elements which are multiples of K by K and count the total number of division operations(say X) performed. Then sort the array and multiply the maximum element of the array X times by K i.e. arr[N-1] = arr[N-1]*KX. Follow the steps below to solve this problem:
- Create a variable total_division = 0, to store a total number of divisions performed.
- Iterate over the range [0, N) using the variable index and perform the following tasks:
- If arr[index] %K = 0, then find out how many times can arr[index] be divided by K and increment total_division that many times.
- Sort the array arr[].
- Run a while loop till total_division > 0 and make arr[N-1] = arr[N-1] * K and decrement total_division.
- Create a variable maximum_sum = 0.
- Iterate over the range [0, N) using the variable index and perform the following tasks:
- Update maximum_sum += arr[index].
- After performing the above steps, print the value of maximum_sum as the answer.
Below is the implementation for the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Utility functionint MaximumSumOperations(int arr[], int N, int K){ if (N == 1) { return arr[0]; } // Variable to count total operations int total_division = 0; // Perform the division operation on // the elements multiple of K for (int index = 0; index < N; index++) { if (arr[index] % K == 0) { while (arr[index] > 1 && arr[index] % K == 0) { arr[index] = arr[index] / K; total_division++; } } } sort(arr, arr + N); // Update maximum element and // decrement total_division while (total_division > 0) { arr[N - 1] = K * arr[N - 1]; total_division--; } int maximum_sum = 0; for (int index = 0; index < N; index++) { maximum_sum += arr[index]; } // Return maximum_sum return maximum_sum;}// Driver Codeint main(){ int arr[5] = { 1, 2, 3, 4, 5 }; int N = 5, K = 2; // Function called cout << MaximumSumOperations(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Utility function static int MaximumSumOperations(int arr[], int N, int K) { if (N == 1) { return arr[0]; } // Variable to count total operations int total_division = 0; // Perform the division operation on // the elements multiple of K for (int index = 0; index < N; index++) { if (arr[index] % K == 0) { while (arr[index] > 1 && arr[index] % K == 0) { arr[index] = arr[index] / K; total_division++; } } } Arrays.sort(arr); // Update maximum element and // decrement total_division while (total_division > 0) { arr[N - 1] = K * arr[N - 1]; total_division--; } int maximum_sum = 0; for (int index = 0; index < N; index++) { maximum_sum += arr[index]; } // Return maximum_sum return maximum_sum; } // Driver code public static void main(String args[]) { int arr[] = { 1, 2, 3, 4, 5 }; int N = 5, K = 2; // Function called System.out.println(MaximumSumOperations(arr, N, K)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach # Utility functiondef MaximumSumOperations(arr, N, K): if (N == 1): return arr[0]; # Variable to count total operations total_division = 0; # Perform the division operation on # the elements multiple of K for index in range(N): if (arr[index] % K == 0): while (arr[index] > 1 and arr[index] % K == 0): arr[index] = arr[index] // K; total_division += 1 arr.sort() # Update maximum element and # decrement total_division while (total_division > 0): arr[N - 1] = K * arr[N - 1]; total_division -= 1 maximum_sum = 0; for index in range(N): maximum_sum += arr[index]; # Return maximum_sum return maximum_sum;# Driver Codearr = [1, 2, 3, 4, 5]N = 5K = 2# Function calledprint(MaximumSumOperations(arr, N, K));# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;class GFG{ // Utility function static int MaximumSumOperations(int []arr, int N, int K) { if (N == 1) { return arr[0]; } // Variable to count total operations int total_division = 0; // Perform the division operation on // the elements multiple of K for (int index = 0; index < N; index++) { if (arr[index] % K == 0) { while (arr[index] > 1 && arr[index] % K == 0) { arr[index] = arr[index] / K; total_division++; } } } Array.Sort(arr); // Update maximum element and // decrement total_division while (total_division > 0) { arr[N - 1] = K * arr[N - 1]; total_division--; } int maximum_sum = 0; for (int index = 0; index < N; index++) { maximum_sum += arr[index]; } // Return maximum_sum return maximum_sum; } // Driver code public static void Main() { int []arr = { 1, 2, 3, 4, 5 }; int N = 5, K = 2; // Function called Console.Write(MaximumSumOperations(arr, N, K)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Utility function function MaximumSumOperations(arr, N, K) { if (N == 1) { return arr[0]; } // Variable to count total operations let total_division = 0; // Perform the division operation on // the elements multiple of K for (let index = 0; index < N; index++) { if (arr[index] % K == 0) { while (arr[index] > 1 && arr[index] % K == 0) { arr[index] = Math.floor(arr[index] / K); total_division++; } } } arr.sort(function (a, b) { return a - b }) // Update maximum element and // decrement total_division while (total_division > 0) { arr[N - 1] = K * arr[N - 1]; total_division--; } let maximum_sum = 0; for (let index = 0; index < N; index++) { maximum_sum += arr[index]; } // Return maximum_sum return maximum_sum; } // Driver Code let arr = [1, 2, 3, 4, 5]; let N = 5, K = 2; // Function called document.write(MaximumSumOperations(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Output
46
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
