Last Updated: 26 Mar, 2021
Special Sum
Easy
Asked in companies
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.
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
Approaches
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’ .
The main idea is to calculate the ‘FIRST_SUM’ and the ‘LAST_SUM’ for every index ‘i’ between [0, N - 1], instead of calculating FIRST_SUM and LAST_SUM for every ‘i’ we can maintain prefix and suffix sum and for every ‘i’ the SPECIAL_SUM(i) = PREFIX(i) + SUFFIX(n - i - 1).
- Maintain an array ‘PREFIX’ that maintains the prefix sum of the given array, PREFIX[0] = ARR[0] and PREFIX[i] = PREFIX[i-1] + ARR[i] for i in the range [1,N-1].
- Maintain an array ‘SUFFIX’ that maintains the suffix sum of the given array, SUFFIX[n-1] = ARR[n-1] and SUFFIX[i] = SUFFIX[i+1] + ARR[i] for i in the range [0, N-2].
- Maintain a variable ‘MIN_SPECIAL_SUM’ which stores the minimum of PREFIX[i] + SUFFIX[n-i-1] over the range of 0, N - 1.
- Since the PREFIX[i+1] stores the sum of first i numbers and SUFFIX[i+1] stores the sum of last i numbers, their sum gives the SPECIAL_SUM as defined in the question.
- Return ‘MIN_SPECIAL_SUM’ .
Similar problems