Given an array arr[] and an integer N, the task is to find a number K from the given array such that if all the elements in the arr greater than K are changed to K then the sum of all the elements in the resulting array will be N. Print -1 if it is not possible.
Examples:
Input: arr[] = {3, 1, 10, 8, 4}, N = 16
Output: 4
If all the elements greater than 4 are changed to 4 then the resulting array will be {3, 1, 4, 4, 4}
Hence the sum will be 16 which is the required value of N.
Input: arr[] = {3, 1, 10, 8, 4}, N = 11
Output: -1
Approach: The idea is to use sorting to solve the above problem.
- First, sort the array in ascending order.
- Then traverse the array and for each element arr[i].
- Assume that all the elements after it has been changed to arr[i] and calculate the sum.
- If it is equal to N then return arr[i].
- If the end of the array is reached then print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return K such that changing// all elements greater than K to K will// make array sum N otherwise return -1int findK(int arr[], int size, int N){ // Sorting the array in increasing order sort(arr, arr + size); int temp_sum = 0; // Loop through all the elements of the array for (int i = 0; i < size; i++) { temp_sum += arr[i]; // Checking if sum of array equals N if (N - temp_sum == arr[i] * (size - i - 1)) { return arr[i]; } } return -1;}// Driver codeint main(){ int arr[] = { 3, 1, 10, 4, 8 }; int size = sizeof(arr) / sizeof(int); int N = 16; cout << findK(arr, size, N); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG { // Function to return K such that changing // all elements greater than K to K will // make array sum N otherwise return -1 static int findK(int arr[], int size, int N) { // Sorting the array in increasing order Arrays.sort(arr); int temp_sum = 0; // Loop through all the elements of the array for (int i = 0; i < size; i++) { temp_sum += arr[i]; // Checking if sum of array equals N if (N - temp_sum == arr[i] * (size - i - 1)) { return arr[i]; } } return -1; } // Driver code public static void main (String[] args) { int []arr = { 3, 1, 10, 4, 8 }; int size = arr.length; int N = 16; System.out.print(findK(arr, size, N)); } }// This code is contributed by AnkitRai01 |
Python
# Python3 implementation of the approach# Function to return K such that changing# all elements greater than K to K will# make array sum N otherwise return -1def findK(arr, size, N): # Sorting the array in increasing order arr = sorted(arr) temp_sum = 0 # Loop through all the elements of the array for i in range(size): temp_sum += arr[i] # Checking if sum of array equals N if (N - temp_sum == arr[i] * (size - i - 1)): return arr[i] return -1# Driver codearr = [3, 1, 10, 4, 8]size = len(arr)N = 16print(findK(arr, size, N))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approachusing System;class GFG { // Function to return K such that changing // all elements greater than K to K will // make array sum N otherwise return -1 static int findK(int []arr, int size, int N) { // Sorting the array in increasing order Array.Sort(arr); int temp_sum = 0; // Loop through all the elements of the array for (int i = 0; i < size; i++) { temp_sum += arr[i]; // Checking if sum of array equals N if (N - temp_sum == arr[i] * (size - i - 1)) { return arr[i]; } } return -1; } // Driver code public static void Main() { int []arr = { 3, 1, 10, 4, 8 }; int size = arr.Length; int N = 16; Console.Write(findK(arr, size, N)); } }// This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return K such that changing // all elements greater than K to K will // make array sum N otherwise return -1 function findK(arr, size, N) { // Sorting the array in increasing order arr.sort(function(a, b){return a - b}); let temp_sum = 0; // Loop through all the elements of the array for (let i = 0; i < size; i++) { temp_sum += arr[i]; // Checking if sum of array equals N if (N - temp_sum == arr[i] * (size - i - 1)) { return arr[i]; } } return -1; } let arr = [ 3, 1, 10, 4, 8 ]; let size = arr.length; let N = 16; document.write(findK(arr, size, N)); // This code is contributed by divyesh07019.</script> |
Output
4
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
Approach : Binary Search
Steps:
- First sort the array in non-decreasing order.
- Then uses binary search to find the maximum value of K.
- The left and right variables are used to keep track of the range of possible values for K.
- The mid variable is the midpoint of this range.
- Inside the while loop, the code calculates the sum of the array after replacing all values greater than mid with mid.
- If this sum == N, then we have found our value of K and break out of the loop.
- If the sum is > N, we update right to be mid – 1, and if the sum is < N, we update left to be mid + 1.
- Finally, the code checks if a valid value of K was found and prints either the value of K or -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <algorithm>#include <iostream>#include <vector>using namespace std;int main(){ int arr[] = { 3, 1, 10, 8, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int N = 11; // sort the array in non-decreasing order sort(arr, arr + n); int left = arr[0]; int right = arr[n - 1]; int K = -1; while (left <= right) { int mid = left + (right - left) / 2; // iterate through the array, replacing all values // greater than mid with mid int sum = 0; for (int i = 0; i < n; i++) { sum += min(arr[i], mid); } // check if the sum is equal to N if (sum == N) { K = mid; break; } else if (sum > N) { right = mid - 1; } else { left = mid + 1; } } if (K == -1) { cout << "-1" << endl; } else { cout << K << endl; } return 0;} |
Java
import java.util.Arrays;public class GFG { public static void main(String[] args) { int[] arr = { 3, 1, 10, 8, 4 }; int n = arr.length; int N = 11; // Sort the array in non-decreasing order Arrays.sort(arr); int left = arr[0]; int right = arr[n - 1]; int K = -1; while (left <= right) { int mid = left + (right - left) / 2; // Iterate through the array, replacing all values // greater than mid with mid int sum = 0; for (int i = 0; i < n; i++) { sum += Math.min(arr[i], mid); } // Check if the sum is equal to N if (sum == N) { K = mid; break; } else if (sum > N) { right = mid - 1; } else { left = mid + 1; } } if (K == -1) { System.out.println("-1"); } else { System.out.println(K); } }} |
Python3
# Python3 implementation of the approach def find_max_K(arr, N): # Sort the array in non-decreasing order arr.sort() n = len(arr) left = arr[0] right = arr[n - 1] K = -1 while left <= right: # Calculate the midpoint using integer division mid = left + (right - left) // 2 # Iterate through the array, replacing all values # greater than mid with mid sum = 0 for i in range(n): sum += min(arr[i], mid) # Check if the sum is equal to N if sum == N: K = mid break elif sum > N: # If the sum is greater than N, search in the left half right = mid - 1 else: # If the sum is less than N, search in the right half left = mid + 1 if K == -1: print("-1") else: print(K)# Driver codearr = [3, 1, 10, 8, 4]N = 11find_max_K(arr, N) |
Javascript
function binarySearch(arr, N) { arr.sort((a, b) => a - b); let left = arr[0]; let right = arr[arr.length - 1]; let K = -1; while (left <= right) { let mid = left + Math.floor((right - left) / 2); let sum = 0; for (let i = 0; i < arr.length; i++) { sum += Math.min(arr[i], mid); } if (sum === N) { K = mid; break; } else if (sum > N) { right = mid - 1; } else { left = mid + 1; } } return K;}const arr = [3, 1, 10, 8, 4];const N = 11;const result = binarySearch(arr, N);if (result === -1) { console.log("-1");} else { console.log(result);} |
Output
-1
Time Complexity: O(nlog(max – min)), where n is the size of the input array.
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!
