Given an array arr[] consisting of N positive integers, the task is to maximize the sum of the array element such that the first element of the array is 1 and the difference between the adjacent elements of the array is at most 1 after performing the following operations:
- Rearrange the array elements in any way.
- Reduce any element to any number that is at least 1.
Examples:
Input: arr[] = {3, 5, 1}
Output: 6
Explanation:
One possible arrangement is {1, 2, 3} having maximum possible sum 6.Input: arr[] = {1, 2, 2, 2, 3, 4, 5}
Output: 19
Explanation:
One possible arrangement is {1, 2, 2, 2, 3, 4, 5} having maximum possible sum 19.
Naive Approach: The simplest approach is to sort the given array then traverse in the sorted array and reduced the element that doesn’t satisfy the given condition.
Time Complexity: O(N * log N), where N is the size of the given array.
Auxiliary Space: O(N)
Efficient Approach: The idea is to use the Hashing concept of storing the frequencies of the elements of the given array. Follow the below steps to solve the problem:
- Create an auxiliary array count[] of size (N+1) to store frequency of arr[i].
- While storing the frequency in count[] and if arr[i] greater than N then increment count[N].
- Initialize the size and ans as 0 that stores the previously selected integer and maximum possible sum respectively.
- Traverse the given array count[] array using variable K and do the following:
- Iterate while a loop for each K until count[K] > 0 and size < K.
- Increment size by 1 and ans by size and reduce count[K] by 1 inside while loop.
- Increment ans with K*count[K] after the while loop ends.
- After the above steps, print the value of ans as the maximum possible sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find maximum possible // sum after changing the array elements // as per the given constraints long maxSum(int a[], int n) { // Stores the frequency of // elements in given array int count[n + 1] = {0}; // Update frequency for(int i = 0; i < n; i++) count[min(a[i], n)]++; // Stores the previously // selected integer int size = 0; // Stores the maximum possible sum long ans = 0; // Traverse over array count[] for(int k = 1; k <= n; k++) { // Run loop for each k while (count[k] > 0 && size < k) { size++; ans += size; count[k]--; } // Update ans ans += k * count[k]; } // Return maximum possible sum return ans; } // Driver Code int main() { // Given array arr[] int arr[] = { 3, 5, 1 }; // Size of array int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << (maxSum(arr, n)); return 0; } // This code is contributed by akhilsaini |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find maximum possible // sum after changing the array elements // as per the given constraints static long maxSum(int[] a) { // Length of given array int n = a.length; // Stores the frequency of // elements in given array int[] count = new int[n + 1]; // Update frequency for (int x : a) count[(Math.min(x, n))]++; // stores the previously // selected integer int size = 0; // Stores the maximum possible sum long ans = 0; // Traverse over array count[] for (int k = 1; k <= n; k++) { // Run loop for each k while (count[k] > 0 && size < k) { size++; ans += size; count[k]--; } // Update ans ans += k * count[k]; } // Return maximum possible sum return ans; } // Driver Code public static void main(String[] args) { // Given array arr[] int[] arr = { 3, 5, 1 }; // Function Call System.out.println(maxSum(arr)); } } |
Python3
# Python3 program for the above approach # Function to find maximum possible # sum after changing the array elements # as per the given constraints def maxSum(a, n): # Stores the frequency of # elements in given array count = [0] * (n + 1) # Update frequency for i in range(0, n): count[min(a[i], n)] += 1 # stores the previously # selected integer size = 0 # Stores the maximum possible sum ans = 0 # Traverse over array count[] for k in range(1, n + 1): # Run loop for each k while (count[k] > 0 and size < k): size += 1 ans += size count[k] -= 1 # Update ans ans += k * count[k] # Return maximum possible sum return ans # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 3, 5, 1 ] # Size of array n = len(arr) # Function Call print(maxSum(arr, n)) # This code is contributed by akhilsaini |
C#
// C# program for the above approach using System; class GFG{ // Function to find maximum possible // sum after changing the array elements // as per the given constraints static long maxSum(int[] a) { // Length of given array int n = a.Length; // Stores the frequency of // elements in given array int[] count = new int[n + 1]; // Update frequency for(int i = 0; i < n; i++) count[(Math.Min(a[i], n))]++; // stores the previously // selected integer int size = 0; // Stores the maximum possible sum long ans = 0; // Traverse over array count[] for(int k = 1; k <= n; k++) { // Run loop for each k while (count[k] > 0 && size < k) { size++; ans += size; count[k]--; } // Update ans ans += k * count[k]; } // Return maximum possible sum return ans; } // Driver Code public static void Main() { // Given array arr[] int[] arr = { 3, 5, 1 }; // Function call Console.Write(maxSum(arr)); } } // This code is contributed by akhilsaini |
Javascript
<script> // Javascript program for the above approach // Function to find maximum possible // sum after changing the array elements // as per the given constraints function maxSum( a, n) { // Stores the frequency of // elements in given array var count = Array(n+1).fill(0); // Update frequency for(var i = 0; i < n; i++) count[(Math.min(a[i], n))]++; // Stores the previously // selected integer var size = 0; // Stores the maximum possible sum var ans = 0; // Traverse over array count[] for(var k = 1; k <= n; k++) { // Run loop for each k while (count[k] > 0 && size < k) { size++; ans += size; count[k]--; } // Update ans ans += k * count[k]; } // Return maximum possible sum return ans; } // Driver Code // Given array arr[] var arr = [ 3, 5, 1 ]; // Size of array var n = arr.length; // Function Call document.write(maxSum(arr, n)); // This code is contributed by noob2000. </script> |
Output:
6
Time Complexity: O(N), where N is the size of the given array. As we are using a loop to traverse the array N times.
Auxiliary Space: O(N), as we are using a extra space for count array.
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!
