Given an array arr[] of size N an integer K, the task is to find the maximize the first element of the array by performing the following operations at most K times:
- Choose a pair of indices i and j (0 ? i, j ? N-1) such that |i ? j| = 1 and arri > 0.
- Set arri = arri ? 1 and arrj = arrj + 1 on those two indices.
Examples:
Input: arr[ ] = {1, 0, 3, 2}, K = 5
Output: 3
Explanation:
One of the possible set of operations can be:
Operation 1: Select i = 3 and j = 2. Therefore, the array modifies to {1, 1, 2, 2}.
Operation 2: Select i = 3 and j = 2. Therefore, the array modifies to {1, 2, 1, 2}.
Operation 3: Select i = 2 and j = 1. Therefore, the array modifies to {2, 1, 1, 2}.
Operation 4: Select i = 2 and j = 1. Therefore, the array modifies to {3, 0, 1, 2}.Input: arr[] = {5, 1}, K = 2
Output: 6
Approach: Follow the steps below to solve the problem:
- At any point, it is optimal to choose indices i and j closest to first element of the array, with i > j.
- Therefore, for every operation, traverse the array from left to right and move the elements closer towards the first element.
- If all the elements are in the first position at some point, stop traversing and print the first array element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to maximize// the first array elementint getMax(int arr[], int N, int K){ // Traverse the array for (int i = 1; i < N; i++) { // Initialize cur_val to a[i] int cur_val = arr[i]; // If all operations // are not over yet while (K >= i) { // If current value is // greater than zero if (cur_val > 0) { // Incrementing first // element of array by 1 arr[0] = arr[0] + 1; // Decrementing current // value of array by 1 cur_val = cur_val - 1; // Decrementing number // of operations by i K = K - i; } // If current value is // zero, then break else break; } } // Print first array element cout << arr[0];}// Driver Codeint main(){ // Given array int arr[] = { 1, 0, 3, 2 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Given K int K = 5; // Prints the maximum // possible value of the // first array element getMax(arr, N, K); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to maximize // the first array element static void getMax(int arr[], int N, int K) { // Traverse the array for (int i = 1; i < N; i++) { // Initialize cur_val to a[i] int cur_val = arr[i]; // If all operations // are not over yet while (K >= i) { // If current value is // greater than zero if (cur_val > 0) { // Incrementing first // element of array by 1 arr[0] = arr[0] + 1; // Decrementing current // value of array by 1 cur_val = cur_val - 1; // Decrementing number // of operations by i K = K - i; } // If current value is // zero, then break else break; } } // Print first array element System.out.print(arr[0]); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1, 0, 3, 2 }; // Size of the array int N = arr.length; // Given K int K = 5; // Prints the maximum // possible value of the // first array element getMax(arr, N, K); }}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to maximize# the first array elementdef getMax(arr, N, K): # Traverse the array for i in range(1, N, 1): # Initialize cur_val to a[i] cur_val = arr[i] # If all operations # are not over yet while (K >= i): # If current value is # greater than zero if (cur_val > 0): # Incrementing first # element of array by 1 arr[0] = arr[0] + 1 # Decrementing current # value of array by 1 cur_val = cur_val - 1 # Decrementing number # of operations by i K = K - i # If current value is # zero, then break else: break # Print first array element print(arr[0])# Driver Codeif __name__ == '__main__': # Given array arr = [ 1, 0, 3, 2 ] # Size of the array N = len(arr) # Given K K = 5 # Prints the maximum # possible value of the # first array element getMax(arr, N, K)# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System;class GFG{ // Function to maximize // the first array element static void getMax(int[] arr, int N, int K) { // Traverse the array for(int i = 1; i < N; i++) { // Initialize cur_val to a[i] int cur_val = arr[i]; // If all operations // are not over yet while (K >= i) { // If current value is // greater than zero if (cur_val > 0) { // Incrementing first // element of array by 1 arr[0] = arr[0] + 1; // Decrementing current // value of array by 1 cur_val = cur_val - 1; // Decrementing number // of operations by i K = K - i; } // If current value is // zero, then break else break; } } // Print first array element Console.Write(arr[0]); } // Driver code static void Main() { // Given array int[] arr = { 1, 0, 3, 2 }; // Size of the array int N = arr.Length; // Given K int K = 5; // Prints the maximum // possible value of the // first array element getMax(arr, N, K); }}// This code is contributed by divyesh072019 |
Javascript
<script>// javascript program for the above approach // Function to maximize // the first array element function getMax(arr , N , K) { // Traverse the array for (i = 1; i < N; i++) { // Initialize cur_val to a[i] var cur_val = arr[i]; // If all operations // are not over yet while (K >= i) { // If current value is // greater than zero if (cur_val > 0) { // Incrementing first // element of array by 1 arr[0] = arr[0] + 1; // Decrementing current // value of array by 1 cur_val = cur_val - 1; // Decrementing number // of operations by i K = K - i; } // If current value is // zero, then break else break; } } // Print first array element document.write(arr[0]); } // Driver Code // Given array var arr = [ 1, 0, 3, 2 ]; // Size of the array var N = arr.length; // Given K var K = 5; // Prints the maximum // possible value of the // first array element getMax(arr, N, K);// This code is contributed by aashish1995</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
