Given an array arr[] consisting of N non-negative elements and an integer X, the task is to make X increments such that the value of array sum when each element is divided by 10, i.e.
is maximized. Print the maximum value of
possible.
Note: The value of any element can’t be increased beyond 1000.
Examples:
Input: N = 4, X = 6, arr[] = {4, 8, 8, 8}
Output: 3
Explanation:
Convert the given array to {4, 10, 10, 10} by incrementing arr[1], arr[2] and arr[3] twice each.
Nowis 0 + 1 + 1 + 1 = 3.
Input: N = 3, X = 122, arr[] = {3, 11, 14}
Output: 15
Approach:
- For all the elements, calculate the number of increments required to increase the number to the next multiple of 10 and store these values in an array, say V.
- Calculate the maximum number of times that an element can be incremented by 10 and keep its value <= 1000 and add this value to a variable, say increments which is initialized to 0.
- Sort the array V to make it non-decreasing.
- Then for each value in V, perform the required moves, and increase some element to the next multiple of 10, this increases the answer by 1.
- Do this, while the total moves performed, do not exceed X.
- After going through all elements of V if still some moves are remaining then add to the answer minimum between increments and (remaining moves)/10 .
Below is the implementation of the above approach:
C++
// C++ program for the above problem #include <bits/stdc++.h> using namespace std; void maximizeval10( int a[], int n, int k) { // initialize variables int increments = 0; int ans = 0; vector< int > v; for ( int i = 0; i < n; i++) { // add the current // contribution of the // element to the answer ans += (a[i] / 10); // if the value is // already maximum // then we can't change it if (a[i] == 1000) continue ; else { // moves required to move // to the next multiple // of 10 v.push_back(10 - a[i] % 10); // no of times we can // add 10 to this value // so that its value // does not exceed 1000. increments += (100 - ((a[i]) / 10) - 1); } } // sort the array sort(v.begin(), v.end()); int sum = 0; for ( int i = 0; i < v.size(); i++) { // adding the values to // increase the numbers // to the next multiple of 10 sum += v[i]; if (sum <= k) { // if the total moves // are less than X then // increase the answer ans++; } else // if the moves exceed // X then we cannot // increase numbers break ; } // if there still remain // some moves if (sum < k) { // remaining moves int remaining = k - sum; // add minimum of increments and // remaining/10 to the // answer ans += min(increments, remaining / 10); } // output the final answer cout << ans; } // Driver Code int main() { int N = 4; int X = 6; int A[N] = { 4, 8, 8, 8 }; maximizeval10(A, N, X); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ public static void maximizeval10( int [] a, int n, int k) { // Initialize variables int increments = 0 ; int ans = 0 ; Vector<Integer> v = new Vector<>(); for ( int i = 0 ; i < n; i++) { // Add the current // contribution of the // element to the answer ans += (a[i] / 10 ); // If the value is // already maximum // then we can't change it if (a[i] == 1000 ) continue ; else { // Moves required to move // to the next multiple // of 10 v.add( 10 - a[i] % 10 ); // No of times we can // add 10 to this value // so that its value // does not exceed 1000. increments += ( 100 - ((a[i]) / 10 ) - 1 ); } } // Sort the array Collections.sort(v); int sum = 0 ; for ( int i = 0 ; i < v.size(); i++) { // Adding the values to // increase the numbers // to the next multiple of 10 sum += v.get(i); if (sum <= k) { // If the total moves // are less than X then // increase the answer ans++; } else // If the moves exceed // X then we cannot // increase numbers break ; } // If there still remain // some moves if (sum < k) { // Remaining moves int remaining = k - sum; // Add minimum of increments and // remaining/10 to the // answer ans += Math.min(increments, remaining / 10 ); } // Output the final answer System.out.print(ans); } // Driver code public static void main(String[] args) { int N = 4 ; int X = 6 ; int A[] = { 4 , 8 , 8 , 8 }; maximizeval10(A, N, X); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above problem def maximizeval10(a, n, k): # Initialize variables increments = 0 ans = 0 v = [] for i in range (n): # Add the current # contribution of the # element to the answer ans + = (a[i] / / 10 ) # If the value is already # maximum then we can't # change it if (a[i] = = 1000 ): continue else : # Moves required to move # to the next multiple # of 10 v.append( 10 - a[i] % 10 ) # No of times we can # add 10 to this value # so that its value # does not exceed 1000. increments + = ( 100 - ((a[i]) / / 10 ) - 1 ); # Sort the array v.sort() sum = 0 for i in range ( len (v)): # Adding the values to # increase the numbers # to the next multiple of 10 sum + = v[i] if ( sum < = k): # If the total moves # are less than X then # increase the answer ans + = 1 else : # If the moves exceed # X then we cannot # increase numbers break # If there still remain # some moves if ( sum < k): # Remaining moves remaining = k - sum # Add minimum of increments # and remaining/10 to the # answer ans + = min (increments, remaining / / 10 ) # Output the final answer print (ans) # Driver Code if __name__ = = "__main__" : N = 4 X = 6 A = [ 4 , 8 , 8 , 8 ] maximizeval10(A, N, X) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ public static void maximizeval10( int [] a, int n, int k) { // Initialize variables int increments = 0; int ans = 0; List< int > v = new List< int >(); for ( int i = 0; i < n; i++) { // Add the current // contribution of the // element to the answer ans += (a[i] / 10); // If the value is // already maximum // then we can't change it if (a[i] == 1000) continue ; else { // Moves required to move // to the next multiple // of 10 v.Add(10 - a[i] % 10); // No of times we can // add 10 to this value // so that its value // does not exceed 1000. increments += (100 - ((a[i]) / 10) - 1); } } // Sort the array v.Sort(); int sum = 0; for ( int i = 0; i < v.Count; i++) { // Adding the values to // increase the numbers // to the next multiple of 10 sum += v[i]; if (sum <= k) { // If the total moves // are less than X then // increase the answer ans++; } else // If the moves exceed // X then we cannot // increase numbers break ; } // If there still remain // some moves if (sum < k) { // Remaining moves int remaining = k - sum; // Add minimum of increments and // remaining/10 to the // answer ans += Math.Min(increments, remaining / 10); } // Output the readonly answer Console.Write(ans); } // Driver code public static void Main(String[] args) { int N = 4; int X = 6; int []A = {4, 8, 8, 8}; maximizeval10(A, N, X); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach function maximizeval10(a,n,k) { // Initialize variables let increments = 0; let ans = 0; let v = []; for (let i = 0; i < n; i++) { // Add the current // contribution of the // element to the answer ans += Math.floor(a[i] / 10); // If the value is // already maximum // then we can't change it if (a[i] == 1000) continue ; else { // Moves required to move // to the next multiple // of 10 v.push(10 - a[i] % 10); // No of times we can // add 10 to this value // so that its value // does not exceed 1000. increments += (100 - (Math.floor(a[i]) / 10) - 1); } } // Sort the array v.sort( function (a,b){ return a-b;}); let sum = 0; for (let i = 0; i < v.length; i++) { // Adding the values to // increase the numbers // to the next multiple of 10 sum += v[i]; if (sum <= k) { // If the total moves // are less than X then // increase the answer ans++; } else // If the moves exceed // X then we cannot // increase numbers break ; } // If there still remain // some moves if (sum < k) { // Remaining moves let remaining = k - sum; // Add minimum of increments and // remaining/10 to the // answer ans += Math.min(increments, Math.floor(remaining / 10)); } // Output the final answer document.write(ans); } // Driver code let N = 4; let X = 6; let A=[4, 8, 8, 8]; maximizeval10(A, N, X); // This code is contributed by avanitrachhadiya2155 </script> |
3
Time Complexity: O(N * log(N))
Auxiliary Space complexity: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!