Given an array of size 
and a number 
. The task is to modify the given array such that:
- The difference between the sum of the array elements before and after modification is exactly equal to S.
- Modified array elements should be non-negative.
- The minimum value in the modified array must be maximized.
- To modify the given array, you can increment or decrement any element of the array.
The task is to find the minimum number of the modified array. If it is not possible then print -1. The minimum number should be as maximum as possible.
Examples:
Input : a[] = {2, 2, 3}, S = 1
Output : 2
Explanation : Modified array is {2, 2, 2}
Input : a[] = {1, 3, 5}, S = 10
Output : -1
An efficient approach is to make a binary search between the minimum and the maximum possible value of the minimum number in a modified array. The minimum possible value is zero and the maximum possible array is minimum number in a given array. If given array elements sum is less than S then answer is not possible. so, print -1. If given array elements sum equals to S then answer will be zero.
Below is the implementation of the above approach:
C++
// CPP program to find the maximum possible// value of the minimum value of// modified array#include <bits/stdc++.h>using namespace std;// Function to find the maximum possible value// of the minimum value of the modified arrayint maxOfMin(int a[], int n, int S){ // To store minimum value of array int mi = INT_MAX; // To store sum of elements of array int s1 = 0; for (int i = 0; i < n; i++) { s1 += a[i]; mi = min(a[i], mi); } // Solution is not possible if (s1 < S) return -1; // zero is the possible value if (s1 == S) return 0; // minimum possible value int low = 0; // maximum possible value int high = mi; // to store a required answer int ans; // Binary Search while (low <= high) { int mid = (low + high) / 2; // If mid is possible then try to increase // required answer if (s1 - (mid * n) >= S) { ans = mid; low = mid + 1; } // If mid is not possible then decrease // required answer else high = mid - 1; } // Return required answer return ans;}// Driver Codeint main(){ int a[] = { 10, 10, 10, 10, 10 }; int S = 10; int n = sizeof(a) / sizeof(a[0]); cout << maxOfMin(a, n, S); return 0;} |
Java
// Java program to find the maximum possible// value of the minimum value of// modified arrayimport java.io.*;class GFG { // Function to find the maximum possible value// of the minimum value of the modified arraystatic int maxOfMin(int a[], int n, int S){ // To store minimum value of array int mi = Integer.MAX_VALUE; // To store sum of elements of array int s1 = 0; for (int i = 0; i < n; i++) { s1 += a[i]; mi = Math.min(a[i], mi); } // Solution is not possible if (s1 < S) return -1; // zero is the possible value if (s1 == S) return 0; // minimum possible value int low = 0; // maximum possible value int high = mi; // to store a required answer int ans=0; // Binary Search while (low <= high) { int mid = (low + high) / 2; // If mid is possible then try to increase // required answer if (s1 - (mid * n) >= S) { ans = mid; low = mid + 1; } // If mid is not possible then decrease // required answer else high = mid - 1; } // Return required answer return ans;}// Driver Code public static void main (String[] args) { int a[] = { 10, 10, 10, 10, 10 }; int S = 10; int n = a.length; System.out.println( maxOfMin(a, n, S)); }//This code is contributed by ajit. } |
Python
# Python program to find the maximum possible# value of the minimum value of# modified array# Function to find the maximum possible value# of the minimum value of the modified arraydef maxOfMin(a, n, S): # To store minimum value of array mi = 10**9 # To store sum of elements of array s1 = 0 for i in range(n): s1 += a[i] mi = min(a[i], mi) # Solution is not possible if (s1 < S): return -1 # zero is the possible value if (s1 == S): return 0 # minimum possible value low = 0 # maximum possible value high = mi # to store a required answer ans=0 # Binary Search while (low <= high): mid = (low + high) // 2 # If mid is possible then try to increase # required answer if (s1 - (mid * n) >= S): ans = mid low = mid + 1 # If mid is not possible then decrease # required answer else: high = mid - 1 # Return required answer return ans# Driver Codea=[10, 10, 10, 10, 10] S = 10n =len(a)print(maxOfMin(a, n, S))#This code is contributed by Mohit kumar 29 |
C#
// C# program to find the maximum possible // value of the minimum value of // modified array using System;class GFG { // Function to find the maximum possible value // of the minimum value of the modified array static int maxOfMin(int []a, int n, int S) { // To store minimum value of array int mi = int.MaxValue; // To store sum of elements of array int s1 = 0; for (int i = 0; i < n; i++) { s1 += a[i]; mi = Math.Min(a[i], mi); } // Solution is not possible if (s1 < S) return -1; // zero is the possible value if (s1 == S) return 0; // minimum possible value int low = 0; // maximum possible value int high = mi; // to store a required answer int ans=0; // Binary Search while (low <= high) { int mid = (low + high) / 2; // If mid is possible then try to increase // required answer if (s1 - (mid * n) >= S) { ans = mid; low = mid + 1; } // If mid is not possible then decrease // required answer else high = mid - 1; } // Return required answer return ans; } // Driver Code public static void Main () { int []a = { 10, 10, 10, 10, 10 }; int S = 10; int n = a.Length; Console.WriteLine(maxOfMin(a, n, S)); } //This code is contributed by Ryuga } |
PHP
<?php// PHP program to find the maximum possible// value of the minimum value of modified array// Function to find the maximum possible value// of the minimum value of the modified arrayfunction maxOfMin($a, $n, $S){ // To store minimum value // of array $mi = PHP_INT_MAX; // To store sum of elements // of array $s1 = 0; for ($i = 0; $i < $n; $i++) { $s1 += $a[$i]; $mi = min($a[$i], $mi); } // Solution is not possible if ($s1 < $S) return -1; // zero is the possible value if ($s1 == $S) return 0; // minimum possible value $low = 0; // maximum possible value $high = $mi; // to store a required answer $ans; // Binary Search while ($low <= $high) { $mid = ($low + $high) / 2; // If mid is possible then try // to increase required answer if ($s1 - ($mid * $n) >= $S) { $ans = $mid; $low = $mid + 1; } // If mid is not possible then // decrease required answer else $high = $mid - 1; } // Return required answer return $ans;}// Driver Code$a = array( 10, 10, 10, 10, 10 );$S = 10;$n = sizeof($a);echo maxOfMin($a, $n, $S);// This code is contributed by akt_mit?> |
Javascript
<script> // Javascript program to find the maximum possible // value of the minimum value of // modified array // Function to find the maximum possible value // of the minimum value of the modified array function maxOfMin(a, n, S) { // To store minimum value of array let mi = Number.MAX_VALUE; // To store sum of elements of array let s1 = 0; for (let i = 0; i < n; i++) { s1 += a[i]; mi = Math.min(a[i], mi); } // Solution is not possible if (s1 < S) return -1; // zero is the possible value if (s1 == S) return 0; // minimum possible value let low = 0; // maximum possible value let high = mi; // to store a required answer let ans=0; // Binary Search while (low <= high) { let mid = parseInt((low + high) / 2, 10); // If mid is possible then try to increase // required answer if (s1 - (mid * n) >= S) { ans = mid; low = mid + 1; } // If mid is not possible then decrease // required answer else high = mid - 1; } // Return required answer return ans; } let a = [ 10, 10, 10, 10, 10 ]; let S = 10; let n = a.length; document.write(maxOfMin(a, n, S)); </script> |
Output:
8
Time Complexity: O(n + logn)
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!
