Data Modelling & AI Data Structure & Algorithm

Minimum removal of elements from end of an array required to obtain sum K

23 June 2025

0

Given an integer K and an array A[] of size N, the task is to create a new array with sum K with minimum number of operations, where in each operation, an element can be removed either from the start or end of A[] and appended to the new array. If it is not possible to generate a new array with sum K, print -1. If there are multiple answers, print any one of them.

Examples

Input: K = 6, A[] = {1, 2, 3, 1, 3}, N = 5
Output: 1 3 2
Explanation: Operation 1: Removing A[0] modifies A[] to {2, 3, 1, 3}. Sum = 1.
Operation 2: Removing A[3] modifies A[] to {2, 1, 3}. Sum = 4.
Operation 3: Removing A[0] modifies A[] to {1, 3}. Sum = 6.

Input: K = 5, A[] = {1, 2, 7}, N = 3
Output: -1

Naive Approach: Follow the steps below to solve the problem:

The task is to find two minimum length subarrays, one from the beginning and one from the end of the array (possibly empty), such that their sum is equal to K.
Traverse the array from the left and calculate the subarray needed to be removed from the right such that the total sum is K.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
  
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find the minimum number of 
// elements required to be removed from 
// the ends of an array to obtain a sum K 
int minSizeArr(int A[], int N, int K) 
{ 
    // Number of elements removed from the 
    // left and right ends of the array 
    int leftTaken = N, rightTaken = N; 
  
    // Sum of left and right subarrays 
    int leftSum = 0, rightSum = 0; 
  
    // No element is taken from left initially 
    for (int left = -1; left < N; left++) { 
  
        if (left != -1) 
            leftSum += A[left]; 
  
        rightSum = 0; 
  
        // Start taking elements from right side 
        for (int right = N - 1; right > left; right--) { 
  
            rightSum += A[right]; 
  
            if (leftSum + rightSum == K) { 
  
                // (left + 1): Count of elements 
                // removed from the left 
                // (N-right): Count of elements 
                // removed from the right 
                if (leftTaken + rightTaken 
                    > (left + 1) + (N - right)) { 
  
                    leftTaken = left + 1; 
                    rightTaken = N - right; 
                } 
                break; 
            } 
            // If sum is greater than K 
            if (leftSum + rightSum > K) 
                break; 
        } 
    } 
  
    if (leftTaken + rightTaken <= N) { 
  
        for (int i = 0; i < leftTaken; i++) 
            cout << A[i] << " "; 
        for (int i = 0; i < rightTaken; i++) 
            cout << A[N - i - 1] << " "; 
    } 
  
    // If it is not possible to obtain sum K 
    else
        cout << -1; 
} 
  
// Driver Code 
int main() 
{ 
    int N = 7; 
  
    // Given Array 
    int A[] = { 3, 2, 1, 1, 1, 1, 3 }; 
  
    // Given target sum 
    int K = 10; 
  
    minSizeArr(A, N, K); 
  
    return 0; 
}

Java

// Java program for the above approach 
import java.util.*; 
class GFG{ 
      
   
// Function to find the minimum number of 
// elements required to be removed from 
// the ends of an array to obtain a sum K 
static void minSizeArr(int A[], int N, int K) 
{ 
    // Number of elements removed from the 
    // left and right ends of the array 
    int leftTaken = N, rightTaken = N; 
    
    // Sum of left and right subarrays 
    int leftSum = 0, rightSum = 0; 
    
    // No element is taken from left initially 
    for (int left = -1; left < N; left++) { 
    
        if (left != -1) 
            leftSum += A[left]; 
    
        rightSum = 0; 
    
        // Start taking elements from right side 
        for (int right = N - 1; right > left; right--) 
        { 
    
            rightSum += A[right]; 
    
            if (leftSum + rightSum == K) { 
    
                // (left + 1): Count of elements 
                // removed from the left 
                // (N-right): Count of elements 
                // removed from the right 
                if (leftTaken + rightTaken 
                    > (left + 1) + (N - right)) { 
    
                    leftTaken = left + 1; 
                    rightTaken = N - right; 
                } 
                break; 
            } 
            // If sum is greater than K 
            if (leftSum + rightSum > K) 
                break; 
        } 
    } 
    
    if (leftTaken + rightTaken <= N) { 
    
        for (int i = 0; i < leftTaken; i++) 
            System.out.print( A[i] + " "); 
        for (int i = 0; i < rightTaken; i++) 
            System.out.print(A[N - i - 1] + " "); 
    } 
    
    // If it is not possible to obtain sum K 
    else
        System.out.print(-1); 
} 
  
  
// Driver code 
public static void main(String[] args) 
{ 
    int N = 7; 
    
    // Given Array 
    int A[] = { 3, 2, 1, 1, 1, 1, 3 }; 
    
    // Given target sum 
    int K = 10; 
    
    minSizeArr(A, N, K); 
} 
} 
  
// This code is contributed by splevel62.

Python3

# Python3 program for the above approach 
  
# Function to find the minimum number of 
# elements required to be removed from 
# the ends of an array to obtain a sum K 
def minSizeArr(A, N, K): 
      
    # Number of elements removed from the 
    # left and right ends of the array 
    leftTaken = N 
    rightTaken = N 
  
    # Sum of left and right subarrays 
    leftSum = 0
    rightSum = 0
  
    # No element is taken from left initially 
    for left in range(-1, N): 
        if (left != -1): 
            leftSum += A[left] 
  
        rightSum = 0
  
        # Start taking elements from right side 
        for right in range(N - 1, left, -1): 
            rightSum += A[right] 
  
            if (leftSum + rightSum == K): 
                  
                # (left + 1): Count of elements 
                # removed from the left 
                # (N-right): Count of elements 
                # removed from the right 
                if (leftTaken + rightTaken >  
                   (left + 1) + (N - right)): 
                    leftTaken = left + 1
                    rightTaken = N - right 
  
                break
  
            # If sum is greater than K 
            if (leftSum + rightSum > K): 
                break
  
    if (leftTaken + rightTaken <= N): 
        for i in range(leftTaken): 
            print(A[i], end = " ") 
              
        for i in range(rightTaken): 
            print(A[N - i - 1], end = " ") 
  
    # If it is not possible to obtain sum K 
    else: 
        print(-1) 
  
# Driver Code 
if __name__ == "__main__": 
  
    N = 7
  
    # Given Array 
    A = [ 3, 2, 1, 1, 1, 1, 3 ] 
  
    # Given target sum 
    K = 10
  
    minSizeArr(A, N, K) 
  
# This code is contributed by ukasp

C#

// C# program for the above approach 
using System; 
  
class GFG { 
      
// Function to find the smallest 
// array that can be removed from 
// the ends of an array to obtain sum K 
static void minSizeArr(int[] A, int N, int K) 
{ 
    
    // Number of elements removed from the 
    // left and right ends of the array 
    int leftTaken = N, rightTaken = N; 
    
    // Sum of left and right subarrays 
    int leftSum = 0, rightSum = 0; 
    
    // No element is taken from left initially 
    for (int left = -1; left < N; left++) { 
    
        if (left != -1) 
            leftSum += A[left]; 
    
        rightSum = 0; 
    
        // Start taking elements from right side 
        for (int right = N - 1; right > left; right--) 
        { 
    
            rightSum += A[right]; 
    
            if (leftSum + rightSum == K) { 
    
                // (left + 1): Count of elements 
                // removed from the left 
                // (N-right): Count of elements 
                // removed from the right 
                if (leftTaken + rightTaken 
                    > (left + 1) + (N - right)) { 
    
                    leftTaken = left + 1; 
                    rightTaken = N - right; 
                } 
                break; 
            } 
            // If sum is greater than K 
            if (leftSum + rightSum > K) 
                break; 
        } 
    } 
    
    if (leftTaken + rightTaken <= N) { 
    
        for (int i = 0; i < leftTaken; i++) 
            Console.Write( A[i] + " "); 
        for (int i = 0; i < rightTaken; i++) 
            Console.Write(A[N - i - 1] + " "); 
    } 
    
    // If it is not possible to obtain sum K 
    else
        Console.Write(-1); 
} 
  
  
    // Driver Code 
    public static void Main() 
    { 
        int N = 7; 
    
    // Given Array 
    int[] A = { 3, 2, 1, 1, 1, 1, 3 }; 
    
    // Given target sum 
    int K = 10; 
    
    minSizeArr(A, N, K); 
    } 
} 
  
// This code is contributed by code_hunt.

Javascript

<script> 
  
// JavaScript program for the above approach 
  
// Function to find the minimum number of 
// elements required to be removed from 
// the ends of an array to obtain a sum K 
function minSizeArr(A, N, K) 
{ 
    // Number of elements removed from the 
    // left and right ends of the array 
    let leftTaken = N, rightTaken = N; 
     
    // Sum of left and right subarrays 
    let leftSum = 0, rightSum = 0; 
     
    // No element is taken from left initially 
    for (let left = -1; left < N; left++) { 
     
        if (left != -1) 
            leftSum += A[left]; 
     
        rightSum = 0; 
     
        // Start taking elements from right side 
        for (let right = N - 1; right > left; right--) 
        { 
     
            rightSum += A[right]; 
     
            if (leftSum + rightSum == K) { 
     
                // (left + 1): Count of elements 
                // removed from the left 
                // (N-right): Count of elements 
                // removed from the right 
                if (leftTaken + rightTaken 
                    > (left + 1) + (N - right)) { 
     
                    leftTaken = left + 1; 
                    rightTaken = N - right; 
                } 
                break; 
            } 
            // If sum is greater than K 
            if (leftSum + rightSum > K) 
                break; 
        } 
    } 
     
    if (leftTaken + rightTaken <= N) { 
     
        for (let i = 0; i < leftTaken; i++) 
            document.write( A[i] + " "); 
        for (let i = 0; i < rightTaken; i++) 
            document.write(A[N - i - 1] + " "); 
    } 
     
    // If it is not possible to obtain sum K 
    else
        document.write(-1); 
} 
       
// Driver code 
    let N = 7; 
     
    // Given Array 
    let A = [ 3, 2, 1, 1, 1, 1, 3 ]; 
     
    // Given target sum 
    let K = 10; 
     
    minSizeArr(A, N, K); 
  
// This code is contributed by souraavghosh0416. 
</script> 

Output:

3 2 3 1 1

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: Follow the steps below to optimize the above approach:

Calculate the sum of elements of the array A[] and store it in a variable, say Total.
The problem can be seen as finding the maximum size subarray with sum (Total – K).
The remaining elements will add up to K.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find the smallest 
// array that can be removed from 
// the ends of an array to obtain sum K 
void minSizeArr(int A[], int N, int K) 
{ 
    int sum = 0; 
    // Sum of complete array 
    for (int i = 0; i < N; i++) 
        sum += A[i]; 
  
    // If given number is greater 
    // than sum of the array 
    if (K > sum) { 
        cout << -1; 
        return; 
    } 
  
    // If number is equal to 
    // the sum of array 
    if (K == sum) { 
        for (int i = 0; i < N; i++) { 
            cout << A[i] << " "; 
        } 
        return; 
    } 
  
    // tar is sum of middle subarray 
    int tar = sum - K; 
  
    // Find the longest subarray 
    // with sum equal to tar 
    unordered_map<int, int> um; 
    um[0] = -1; 
  
    int left, right; 
    int cur = 0, maxi = -1; 
    for (int i = 0; i < N; i++) { 
        cur += A[i]; 
        if (um.find(cur - tar) != um.end() 
            && i - um[cur - tar] > maxi) { 
            maxi = i - um[cur - tar]; 
            right = i; 
            left = um[cur - tar]; 
        } 
        if (um.find(cur) == um.end()) 
            um[cur] = i; 
    } 
  
    // If there is no subarray with 
    // sum equal to tar 
    if (maxi == -1) 
        cout << -1; 
  
    else { 
        for (int i = 0; i <= left; i++) 
            cout << A[i] << " "; 
        for (int i = 0; i < right; i++) 
            cout << A[N - i - 1] << " "; 
    } 
} 
  
// Driver Code 
int main() 
{ 
    int N = 7; 
  
    // Given Array 
    int A[] = { 3, 2, 1, 1, 1, 1, 3 }; 
  
    // Given target sum 
    int K = 10; 
  
    minSizeArr(A, N, K); 
    return 0; 
}

Java

// Java program for the above approach 
import java.io.*; 
import java.util.*; 
  
class GFG { 
    
      // Function to find the smallest 
// array that can be removed from 
// the ends of an array to obtain sum K 
static void minSizeArr(int A[], int N, int K) 
{ 
    int sum = 0; 
    
    // Sum of complete array 
    for (int i = 0; i < N; i++) 
        sum += A[i]; 
  
    // If given number is greater 
    // than sum of the array 
    if (K > sum) { 
        System.out.print(-1); 
        return; 
    } 
  
    // If number is equal to 
    // the sum of array 
    if (K == sum) { 
        for (int i = 0; i < N; i++) { 
            System.out.print(A[i] + " "); 
        } 
        return; 
    } 
  
    // tar is sum of middle subarray 
    int tar = sum - K; 
  
    // Find the longest subarray 
    // with sum equal to tar 
    HashMap<Integer, Integer> um = new HashMap<Integer, Integer>(); 
     um.put(0, -1); 
  
    int left = 0, right = 0; 
    int cur = 0, maxi = -1; 
    for (int i = 0; i < N; i++) { 
        cur += A[i]; 
        if (um.containsKey(cur - tar) 
            && i - um.get(cur - tar) > maxi) { 
            maxi = i - um.get(cur - tar); 
            right = i; 
            left = um.get(cur - tar); 
        } 
        if (!um.containsKey(cur)) 
            um.put(cur, i); 
    } 
  
    // If there is no subarray with 
    // sum equal to tar 
    if (maxi == -1) 
        System.out.println(-1); 
  
    else { 
        for (int i = 0; i <= left; i++) 
            System.out.print(A[i] + " "); 
        for (int i = 0; i < right; i++) 
            System.out.print(A[N - i - 1] + " "); 
    } 
} 
  
// Driver Code 
    public static void main (String[] args) { 
        int N = 7; 
  
    // Given Array 
    int A[] = { 3, 2, 1, 1, 1, 1, 3 }; 
  
    // Given target sum 
    int K = 10; 
  
    minSizeArr(A, N, K); 
    } 
} 
  
// This code is contributed by Dharanendra L V.

Python3

# python 3 program for the above approach 
  
# Function to find the smallest 
# array that can be removed from 
# the ends of an array to obtain sum K 
def minSizeArr(A, N, K): 
    sum = 0
      
    # Sum of complete array 
    for i in range(N): 
        sum += A[i] 
  
    # If given number is greater 
    # than sum of the array 
    if (K > sum): 
        print(-1); 
        return
  
    # If number is equal to 
    # the sum of array 
    if (K == sum): 
        for i in range(N): 
            print(A[i],end = " ") 
        return
  
    # tar is sum of middle subarray 
    tar = sum - K 
  
    # Find the longest subarray 
    # with sum equal to tar 
    um = {} 
    um[0] = -1
  
    left = 0
    right = 0
    cur = 0
    maxi = -1
    for i in range(N): 
        cur += A[i] 
        if((cur - tar) in um and (i - um[cur - tar]) > maxi): 
            maxi = i - um[cur - tar] 
            right = i 
            left = um[cur - tar] 
        if(cur not in um): 
            um[cur] = i 
  
    # If there is no subarray with 
    # sum equal to tar 
    if (maxi == -1): 
        print(-1) 
  
    else: 
        for i in range(left+1): 
            print(A[i], end = " ") 
        for i in range(right): 
            print(A[N - i - 1], end = " ") 
  
# Driver Code 
if __name__ == '__main__': 
    N = 7
      
    # Given Array 
    A = [3, 2, 1, 1, 1, 1, 3] 
      
    # Given target sum 
    K = 10
    minSizeArr(A, N, K) 
      
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# program for 
// the above approach 
using System; 
using System.Collections.Generic;   
  
class GFG{ 
      
// Function to find the smallest 
// array that can be removed from 
// the ends of an array to obtain sum K 
static void minSizeArr(int[] A, int N, int K) 
{ 
    int sum = 0; 
    
    // Sum of complete array 
    for(int i = 0; i < N; i++) 
        sum += A[i]; 
  
    // If given number is greater 
    // than sum of the array 
    if (K > sum) 
    { 
        Console.WriteLine(-1); 
        return; 
    } 
  
    // If number is equal to 
    // the sum of array 
    if (K == sum)  
    { 
        for(int i = 0; i < N; i++)  
        { 
           Console.Write(A[i] + " "); 
        } 
        return; 
    } 
  
    // tar is sum of middle subarray 
    int tar = sum - K; 
  
    // Find the longest subarray 
    // with sum equal to tar 
    Dictionary<int,  
               int> um =  new Dictionary<int, 
                                         int>();  
     um[0] = -1; 
  
    int left = 0, right = 0; 
    int cur = 0, maxi = -1; 
    for(int i = 0; i < N; i++)  
    { 
        cur += A[i]; 
        if (um.ContainsKey(cur - tar) &&  
             i - um[cur - tar] > maxi)  
        { 
            maxi = i - um[cur - tar]; 
            right = i; 
            left = um[cur - tar]; 
        } 
        if (!um.ContainsKey(cur)) 
            um[cur] = i; 
    } 
  
    // If there is no subarray with 
    // sum equal to tar 
    if (maxi == -1) 
        Console.Write(-1); 
  
    else 
    { 
        for(int i = 0; i <= left; i++) 
            Console.Write(A[i] + " "); 
        for(int i = 0; i < right; i++) 
            Console.Write(A[N - i - 1] + " "); 
    } 
}    
  
// Driver code 
static public void Main() 
{ 
    int N = 7; 
      
    // Given Array 
    int[] A = { 3, 2, 1, 1, 1, 1, 3 }; 
      
    // Given target sum 
    int K = 10; 
      
    minSizeArr(A, N, K); 
} 
} 
  
// This code is contributed by offbeat

Javascript

<script> 
  
// JavaScript program for the above approach 
  
// Function to find the smallest 
// array that can be removed from 
// the ends of an array to obtain sum K 
function minSizeArr(A, N, K) 
{ 
    var sum = 0; 
    var i; 
    // Sum of complete array 
    for (i = 0; i < N; i++) 
        sum += A[i]; 
  
    // If given number is greater 
    // than sum of the array 
    if (K > sum) { 
        cout << -1; 
        return; 
    } 
  
    // If number is equal to 
    // the sum of array 
    if (K == sum) { 
        for (i = 0; i < N; i++) { 
            document.write(A[i]+' '); 
        } 
        return; 
    } 
  
    // tar is sum of middle subarray 
    var tar = sum - K; 
  
    // Find the longest subarray 
    // with sum equal to tar 
    var um = new Map(); 
    um[0] = -1; 
  
    var left, right; 
    var cur = 0, maxi = -1; 
    for (i = 0; i < N; i++) { 
        cur += A[i]; 
        if (um.has(cur - tar) 
            && i - um.get(cur - tar) > maxi) { 
            maxi = i - um.get(cur - tar); 
            right = i; 
            left = um.get(cur - tar); 
        } 
        if (!um.has(cur)) 
            um.set(cur,i); 
    } 
  
    // If there is no subarray with 
    // sum equal to tar 
    if (maxi == -1) 
        cout << -1; 
  
    else { 
        for (i = 0; i <= left; i++) 
            document.write(A[i]+' '); 
        for (i = 0; i < right; i++) 
            document.write(A[N - i - 1]+ ' '); 
    } 
} 
  
// Driver Code 
  
    var N = 7; 
  
    // Given Array 
    var A = [3, 2, 1, 1, 1, 1, 3]; 
  
    // Given target sum 
    var K = 10; 
  
    minSizeArr(A, N, K); 
  
</script>

Output:

3 2 3 1 1

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Minimum removal of elements from end of an array required to obtain sum K

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

Philips Hue expands smart lighting lineup with doorbell, string lights, and budget bulbs

Early Galaxy S26 leak hints at one big surprise in the design department

I had trouble playing Hollow Knight: Silksong at release because of how popular it is

US users miss out on the Galaxy S25 FE’s best storage option

EDITOR PICKS

Philips Hue expands smart lighting lineup with doorbell, string lights, and budget bulbs

Early Galaxy S26 leak hints at one big surprise in the design department

I had trouble playing Hollow Knight: Silksong at release because of how popular it is

POPULAR POSTS

Philips Hue expands smart lighting lineup with doorbell, string lights, and budget bulbs

Early Galaxy S26 leak hints at one big surprise in the design department

I had trouble playing Hollow Knight: Silksong at release because of how popular it is

POPULAR CATEGORY

ABOUT US

FOLLOW US