Maximize the last Array element as per the given conditions
Given an array arr[] consisting of N integers, rearrange the array such that it satisfies the following conditions:
- arr[0] must be 1.
- Difference between adjacent array elements should not exceed 1, that is, arr[i] – arr[i-1] ? 1 for all 1 ? i < N.
The permissible operations are as follows:
- Rearrange the elements in any way.
- Reduce any element to any number ? 1.
The task is to find the maximum possible value that can be placed at the last index of the array.
Examples:
Input: arr[] = {3, 1, 3, 4}
Output: 4
Explanation:
Subtracting 1 from the first element modifies the array to {2, 1, 3, 4}.
Swapping the first two elements modifies the array to {1, 2, 3, 4}.
Therefore, maximum value placed at the last index is 4.
Input: arr[] = {1, 1, 1, 1}
Output: 1
Approach:
To solve the given problem, sort the given array and balance it according to the given condition starting from left towards right. Follow the below steps to solve the problem:
- Sort the array in ascending order.
- If the first element is not 1, make it 1.
- Traverse the array over the indices [1, N – 1) and check if every adjacent element has a difference of ? 1.
- If not, decrement the value till the difference becomes ? 1.
- Return the last element of the array.
Below is the implementation of the above problem:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum possible value // that can be placed at the last index int maximizeFinalElement( int arr[], int n) { // Sort array in ascending order sort(arr, arr + n); // If the first element // is not equal to 1 if (arr[0] != 1) arr[0] = 1; // Traverse the array to make // difference between adjacent // elements <=1 for ( int i = 1; i < n; i++) { if (arr[i] - arr[i - 1] > 1) { arr[i] = arr[i - 1] + 1; } } return arr[n - 1]; } // Driver Code int main() { int n = 4; int arr[] = { 3, 1, 3, 4 }; int max = maximizeFinalElement(arr, n); cout << max; return 0; } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to find the maximum possible value // that can be placed at the last index public static int maximizeFinalElement( int arr[], int n) { // Sort the array elements // in ascending order Arrays.sort(arr); // If the first element is // is not equal to 1 if (arr[ 0 ] != 1 ) arr[ 0 ] = 1 ; // Traverse the array to make // difference between adjacent // elements <=1 for ( int i = 1 ; i < n; i++) { if (arr[i] - arr[i - 1 ] > 1 ) { arr[i] = arr[i - 1 ] + 1 ; } } return arr[n - 1 ]; } // Driver Code public static void main (String[] args) { int n = 4 ; int arr[] = { 3 , 1 , 3 , 4 }; int max = maximizeFinalElement(arr, n); System.out.print(max); } } |
Python3
# Python3 program to implement # the above approach # Function to find the maximum possible value # that can be placed at the last index def maximizeFinalElement(arr, n): # Sort the array elements # in ascending order arr.sort(); # If the first element is # is not equal to 1 if (arr[ 0 ] ! = 1 ): arr[ 0 ] = 1 ; # Traverse the array to make # difference between adjacent # elements <=1 for i in range ( 1 , n): if (arr[i] - arr[i - 1 ] > 1 ): arr[i] = arr[i - 1 ] + 1 ; return arr[n - 1 ]; # Driver Code if __name__ = = '__main__' : n = 4 ; arr = [ 3 , 1 , 3 , 4 ]; max = maximizeFinalElement(arr, n); print ( max ); # This code is contributed by Princi Singh |
C#
// C# Program to implement // the above approach using System; class GFG{ // Function to find the maximum possible value // that can be placed at the last index public static int maximizeFinalElement( int []arr, int n) { // Sort the array elements // in ascending order Array.Sort(arr); // If the first element is // is not equal to 1 if (arr[0] != 1) arr[0] = 1; // Traverse the array to make // difference between adjacent // elements <=1 for ( int i = 1; i < n; i++) { if (arr[i] - arr[i - 1] > 1) { arr[i] = arr[i - 1] + 1; } } return arr[n - 1]; } // Driver Code public static void Main(String[] args) { int n = 4; int []arr = { 3, 1, 3, 4 }; int max = maximizeFinalElement(arr, n); Console.WriteLine(max); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the maximum possible value // that can be placed at the last index function maximizeFinalElement(arr, n) { // Sort array in ascending order arr.sort((a, b) => a - b); // If the first element // is not equal to 1 if (arr[0] != 1) arr[0] = 1; // Traverse the array to make // difference between adjacent // elements <=1 for (let i = 1; i < n; i++) { if (arr[i] - arr[i - 1] > 1) { arr[i] = arr[i - 1] + 1; } } return arr[n - 1]; } // Driver Code let n = 4; let arr = [ 3, 1, 3, 4 ]; let max = maximizeFinalElement(arr, n); document.write(max); // This code is contributed by Surbhi Tyagi. </script> |
4
Time Complexity: O(NlogN)
Auxiliary Space: O(N)