Data Modelling & AI Data Structure & Algorithm

Find K such that changing all elements of the Array greater than K to K will make array sum N

23 June 2025

0

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 -1
int 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 code
int 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 -1
def 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 code
arr = [3, 1, 10, 4, 8]
size = len(arr)
N = 16
 
print(findK(arr, size, N))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the above approach
using 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

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 code
arr = [3, 1, 10, 8, 4]
N = 11
find_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!

Find K such that changing all elements of the Array greater than K to K will make array sum N

C++

Java

Python

C#

Javascript

Approach : Binary Search

C++

Java

Python3

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US