Given an array, arr[] and two integers, K and X, the task is to maximize the sum of the array elements after at most K increments of any elements, then dividing all of the elements by X
Example:
Input: arr = {16, 15, 17}, K = 8, X = 10
Output: 5
Explanation: At most 8 increments are allowed. So, increment element at index 0 by 4 and element at index 2 by 3. So the modified array becomes {20/10, 15/10, 20/10} = {2, 1, 2}, therefore the sum is 2+1+2 = 5Input: arr = {8, 13, 2, 4, 7}, K = 6, X = 5
Output: 7
Approach: The given problem can be solved by using a greedy approach. The idea is to sort the array by tweaking the comparator in such a way that the elements which need the least increment to become divisible by X are encountered first. Follow the steps below to solve the problem:
- Sort the ArrayList in the order where elements having the greater remainder after dividing by X are encountered first
- Iterate the ArrayList and at every iteration:
- Find the remaining value rem to be added to arr[i], such that it becomes a multiple of X
- If K < rem, then break the loop
- Else increment arr[i] with rem and decrement K by rem
- Find the remaining value rem to be added to arr[i], such that it becomes a multiple of X
- Initialize a variable sum to 0
- Traverse the ArrayList and at every iteration:
- Add arr[i] / X to the sum
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;int x = 5;static bool cmp(int a, int b) { return (b % x) < (a % x); }int maxSumIncDiv(vector<int> nums, int k){ // Sort in such a way that the // numbers needing least increment // to become multiple of x are // encountered first sort(nums.begin(), nums.end(), cmp); // Iterate the ArrayList for (int i = 0; i < nums.size(); i++) { int rem = nums[i] % x; // Find the value to increment // current element such that it // becomes a multiple of x rem = x - rem; // Incrementing any element with // the remaining value of k will // have no effect if (k < rem) { break; } else { // Increment element so that // it becomes multiple of x nums[i] = nums[i] + rem; // Decrement k by the // remaining value k -= rem; } } // Initialize sum int sum = 0; // Traverse the ArrayList for (int i = 0; i < nums.size(); i++) { // calculate sum of elements // divided by x sum += nums[i] / x; } // Return the answer return sum;}int main(){ // Initializing list of nums vector<int> nums = { 8, 13, 2, 4, 7 }; int K = 6; // Call the function and // print the answer cout << (maxSumIncDiv(nums, K)); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approachimport java.util.*;import java.io.*;class GFG { public static int maxSumIncDiv( List<Integer> nums, int k, int x) { // Sort in such a way that the // numbers needing least increment // to become multiple of x are // encountered first Collections.sort( nums, (a, b) -> b % x - a % x); // Iterate the ArrayList for (int i = 0; i < nums.size(); i++) { int rem = nums.get(i) % x; // Find the value to increment // current element such that it // becomes a multiple of x rem = x - rem; // Incrementing any element with // the remaining value of k will // have no effect if (k < rem) { break; } else { // Increment element so that // it becomes multiple of x nums.set(i, nums.get(i) + rem); // Decrement k by the // remaining value k -= rem; } } // Initialize sum int sum = 0; // Traverse the ArrayList for (int i = 0; i < nums.size(); i++) { // calculate sum of elements // divided by x sum += nums.get(i) / x; } // Return the answer return sum; } public static void main(String[] args) { // Initializing list of nums List<Integer> nums = new ArrayList<>(); int K = 6, X = 5; nums.add(8); nums.add(13); nums.add(2); nums.add(4); nums.add(7); // Call the function and // print the answer System.out.println( maxSumIncDiv(nums, K, X)); }} |
Python3
# Python implementation for the above approachimport mathdef maxSumIncDiv(nums, k, x): # Sort in such a way that the # numbers needing least increment # to become multiple of x are # encountered first nums.sort(); # Iterate the ArrayList for i in range(len(nums)): rem = nums[i] % x; # Find the value to increment # current element such that it # becomes a multiple of x rem = x - rem; # Incrementing any element with # the remaining value of k will # have no effect if (k < rem): break; else: # Increment element so that # it becomes multiple of x nums[i] = nums[i] + rem; # Decrement k by the # remaining value k -= rem; # Initialize sum sum = 0; # Traverse the ArrayList for i in range(len(nums)): # calculate sum of elements # divided by x sum += nums[i] / x; # Return the answer return math.floor(sum) # Initializing list of numsnums = [];K = 6X = 5nums.append(8);nums.append(13);nums.append(2);nums.append(4);nums.append(7);# Call the function and# print the answerprint(maxSumIncDiv(nums, K, X)); # This code is contributed by gfgking. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ public static int maxSumIncDiv( List<int> nums, int k, int x) { // Sort in such a way that the // numbers needing least increment // to become multiple of x are // encountered first nums.Sort((a, b) => b % x - a % x); // Iterate the ArrayList for (int i = 0; i < nums.Count; i++) { int rem = nums[i] % x; // Find the value to increment // current element such that it // becomes a multiple of x rem = x - rem; // Incrementing any element with // the remaining value of k will // have no effect if (k < rem) { break; } else { // Increment element so that // it becomes multiple of x nums[i] = nums[i] + rem; // Decrement k by the // remaining value k -= rem; } } // Initialize sum int sum = 0; // Traverse the ArrayList for (int i = 0; i < nums.Count; i++) { // calculate sum of elements // divided by x sum += nums[i] / x; } // Return the answer return (sum); }// Driver Codepublic static void Main(String[] args){ // Initializing list of nums List<int> nums = new List<int>(); int K = 6, X = 5; nums.Add(8); nums.Add(13); nums.Add(2); nums.Add(4); nums.Add(7); // Call the function and // print the answer Console.Write( maxSumIncDiv(nums, K, X));}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript implementation for the above approachfunction maxSumIncDiv(nums, k, x) { // Sort in such a way that the // numbers needing least increment // to become multiple of x are // encountered first nums.sort((a, b) => b % x - a % x); // Iterate the ArrayList for (var i = 0; i < nums.length; i++) { var rem = nums[i] % x; // Find the value to increment // current element such that it // becomes a multiple of x rem = x - rem; // Incrementing any element with // the remaining value of k will // have no effect if (k < rem) { break; } else { // Increment element so that // it becomes multiple of x nums[i] = nums[i] + rem; // Decrement k by the // remaining value k -= rem; } } // Initialize sum var sum = 0; // Traverse the ArrayList for (var i = 0; i < nums.length; i++) { // calculate sum of elements // divided by x sum += nums[i] / x; } // Return the answer return parseInt(sum); }// Initializing list of numsvar nums = [];var K = 6, X = 5;nums.push(8);nums.push(13);nums.push(2);nums.push(4);nums.push(7);// Call the function and// print the answerdocument.write( maxSumIncDiv(nums, K, X)); // This code is contributed by rutvik_56.</script> |
Output
7
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Share your thoughts in the comments
