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!
