Maximum Adjacent Sum of a Circular array

Moderate
0/80
Average time to solve is 38m
profile
Contributed by
0 upvote

Problem statement

You are given a circular array of integers ‘NUMS’ of length ‘N’. You need to choose some elements from the array in such a way that between every pair of adjacent elements you have chosen at least one of them.

Choose the elements optimally and return the minimum sum of the chosen elements.

Example: 
Input: ‘N’ = 5,  ‘NUMS’ = {1, 2, 3, 5, 2}.

Output: 6.


The indices of the chosen elements are [0, 2, 4], hence sum = 1 + 3 + 2 = 6.
Note: Some of the invalid ways to choose the elements are: 
Choose the elements with indices (0, 4), it is invalid because, among the pair of indices (1, 2) none of them were chosen. 
Choose the elements with indices (0, 2), it is invalid because, among the pair of indices (3, 4) none of them were chosen. 
Choose the elements with indices (1, 2), it is invalid because, among the pair of indices (0, 4) none of them were chosen.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the length of the array ‘NUMS. 

The second line of each test case contains ‘N’ space-separated integers.
Output format : 
For each test case, you don’t need to print anything just return the minimum adjacent sum
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^6 
0 <= NUMS[ i ] <= 10^3
Sum of N Over all the Test cases <= 10^6

Time Limit: 1 sec
Sample Input 1 :
2
5
1 1 2 1 2
3
2 2 2
Sample Output 1 :
3
4
Explanation Of Sample Input 1 :
For the first case:
Choose the elements with the indices (0, 1, 3), hence sum = 1 + 1 + 1 = 3.

For the second case:
Choose the elements with the indices (0, 1), hence sum = 2 + 2 = 4.
Sample Input 2 :
2
6
15 100 23 23 1 15
7
101 110 123 11 12 1 2
Sample Output 2 :
39
124
Hint

Can you think of a way to solve this problem using recursion?

Approaches (3)
Recursion

In this approach, the idea is to use recursion to optimally find the solution. At each element, we have two choices, either we choose that element or we don’t. Since this is a circular array so we need to take care of the case that when we are including the 0th element then we may or may not choose (‘N’ - 1)th element or when we don’t choose the 0th element then we need to choose the (‘N’ - 1)th element.


 

We can address this problem by first definitely including the 0th element and then recursively finding the minimum sum from the rest of the element and then we definitely include the (‘N’ - 1)th element and then recursively finding the minimum sum from the rest of the element. The minimum sum is given by the minimum of ( the value we got from  including the 0th, the value we got from including the  (‘N’ - 1)th element),


 

To recursively find the minimum sum we can make a recursive function, let the function be ‘F’, the function has two parameters, the index of the elements we are at and a flag value that denotes whether the last element was chosen or not.


 

If flag = 1 then (i.e, last value was not chosen)

F( idx, flag ) = ‘NUMS[ idx]’ + ‘F( idx+1, 0 ).

Else:

F( idx, flag) = min(  ‘NUMS[ idx]’ + ‘F( idx+1, 0 ), F( idx + 1, 1) ).


 

The steps are as follows:-

// Recursive function to get minimum sum.

Function getMinUtil( [ int ] nums, int idx, int flag):

  1. If the value of 'IDX' is 'N' then return 0.
  2. If the value of 'FLAG' is 1 choose the current element and recursively call the 'getMinUtil' function to choose the other elements. Return the sum of these values.
  3. Else return the minimum value by either choosing the element or not choosing the element.


 

Function getMinCost( [ int ] nums):

  1. Create an array 'EXCLUDE0' and assign all the values of 'NUMS' excluding value at 0.
  2. Create an array 'EXCLUDEN' and assign all the values of 'NUMS' excluding value at 'N' - 1.
  3. Initialize a variable 'ANS' with value of 'NUMS[ 0 ]' + the value returned by the recursive function 'getMinUtil' by passing the array 'EXCLUDE0' and ‘FLAG’ as 0 in the argument.
  4. Update the value of 'ANS' with the minimum of 'ANS' and ( 'NUMS[ N - 1 ] + the value returned the recursive function 'getMinUtil' by passing the array 'EXCLUDEN' and ‘FLAG’ as 0 in the argument).
  5. Return the value of 'ANS'.
Time Complexity

O( 2 ^ N  ), Where ‘N’ is the length of the array ’NUMS’.

 

For each element, we have two choices either we choose it or we do not choose it. We are exploring all the possibilities to find the minimum sum. The recursive tree grows as 1, 2, 4, …. 2^N

Hence the time complexity is  O( 2 ^ N ).

Space Complexity

O( N ),

 

We using two extra arrays ‘EXLUDE0’ and ‘EXCLUDEN’. 

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Maximum Adjacent Sum of a Circular array
Full screen
Console