Special Sum

Easy
0/40
Average time to solve is 15m
17 upvotes
Asked in companies
SamsungHexaview Techalibaba

Problem statement

You are given an array ‘ARR’ of length ‘N’. There are two operations, ‘FIRST_SUM’ and ‘LAST_SUM’ for every index ‘i’ (1 <= i <= N) in the array,

i) FIRST_SUM(i) calculates the sum of first i numbers.

ii) LAST_SUM(i) calculates the sum of last N-i+1 numbers.

Also for every ‘i’, SPECIAL_SUM(i) can be calculated as:

SPECIAL_SUM(i) = FIRST_SUM(i) + LAST_SUM(i)

Your task is to return the minimum SPECIAL_SUM for 0 <= i <= N - 1.

For example:

Given ‘N’ = 4 and ‘ARR’ = [1, 2, 3, 4].
Then the minimum special sum will be 5 for i = 0 (0-based indexing), which is (1 + 4) = 5.Sum of 1 integer from beginning and end.
For i = 1 it will be (1 + 2) + (3 + 4) = 10
For i = 2 it will be (1 + 2 + 3) + (2 + 3 + 4) = 15
For i = 3 it will be (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4) = 20
All of which are greater than 5.
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer N, where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output format:

For each test case, return the minimum SPECIAL_SUM for ‘i’ in the range [ 0, N-1 ].

The output of each test case will be printed in a separate line.

Note:

You don’t need to print anything. You just need to implement the given function.

Constraints:

1 <= T <= 5
1 <=  N <= 5 *10^3
-5 *10^2 <= ARR[i] < 5 *10^2

Time limit: 1 sec

Sample Input 1:

2
4
1 2 3 4
4
1 -2 -3 4

Sample Output 1:

5
-5

Explanation of the Sample Input 1:

For the first test case:
The  minimum special sum will be 5 for i = 0 (0-based indexing), which is (1 + 4) = 5.
For i = 1 it will be (1 + 2) + (3 + 4) = 10
For i = 2 it will be (1 + 2 + 3) + (2 + 3 + 4) = 15
For i = 3 it will be (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4) = 20
All of which are greater than 5.  

For the second test case:
The  minimum special sum will be -5 for i = 2 (0-based indexing), which is (1 + (-2) + (-3)) +  (-2 + (-3) + (4)) = -5.
For i = 0 it will be (1) + (4) = 5
For i = 1 it will be (1 + (-2) ) + ( (-3) + 4) = 0 
For i = 3 it will be (1 + (-2) + (-3) + 4)  + (1 + (-2) + (-3) + 4) = 0.
All of which are less than -5.

Sample Input 2:

2
5
1 2 -5 3 1
5 
1 1 1 1 1

Sample Output 2:

-3
2
Hint

 Do we need to calculate firstSum and lastSum for every i?

Approaches (2)
Brute force

The main idea is to calculate the ‘FIRST_SUM’ and the ‘LAST_SUM’ for every index ‘i’ between [0, N - 1].

 

  • FIRST_SUM can be calculated easily by looping from range 0 to the ‘ith’ number we want and adding all of the numbers.
  • Similarly, LAST_SUM can be calculated easily by looping from (N - 1)th element to the (N - i - 1)th element and adding all the numbers in between.
  • Maintain a variable ‘MIN_SPECIAL_SUM’ which stores the minimum of ‘FIRST_SUM’ + ‘LAST_SUM’ over the range of 0, (N - 1).
  • Return ‘MIN_SPECIAL_SUM’ .
Time Complexity

O(N ^ 2), where ‘N’ is the length of the given array.

 

We have to traverse the array N times. Therefore, the net time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

Since we are not using any extra space to keep track of the elements.

Code Solution
(100% EXP penalty)
Special Sum
Full screen
Console