Pizza Sharing

Moderate
0/80
4 upvotes
Asked in companies
MicrosoftSamsung

Problem statement

Ninja and his two friends went to a picnic and enjoy their pizza. But they found that the slices of pizza are not uniform. Ninja is very hungry so he wants to take the bigger slices of pizza. So all friends decided to follow the rule while eating pizza:

1 . Ninja will pick a slice of pizza.
2 . One of his friends will pick the next slice in the anti-clockwise direction.
3 . the Second friend will pick the next slice in the clockwise direction of Ninja’s pick.

You are given an array ‘ARR’ having the weights of ‘N’ slices representing a circular array in the clockwise direction.N is a multiple of 3. Ninja wants to collect the slices such that their sum is maximum. Can you help Ninja to solve this problem and tell him the maximum sum he can achieve?

For Example 
If the ARR is [4,3,11,12,2,4] , so the optimal answer will be as follows:
Ninja will pick the slice having weight 12, so his friends will pick the slices having weights 11 and 2. After that Ninja will pick the slice with weight 4 and his friends will pick 4 and 3.
Ninja’s sum will be 16 which is the maximum.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

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

The following line contains ‘N’ values corresponding to elements of ‘ARR’.
Output Format: 
For each test case, print the maximum sum of the weight of slices.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 1000.
1 <=ARR[i] <=10^6.

Time limit: 1 sec
Sample Input 1:
2
6
4 3 11 12 2 4
6
1 2 3 4 5 6
Sample Output 1:
16
10
Explanation of sample input 1:
For the first test case,

Ninja will pick the slice having weight 12, so his friends will pick the slices having weights 11 and 2. After that Ninja will pick the slice with weight 4 and his friends will pick 4 and 3.
Ninja’s sum will be 16 which is the maximum.
Hence, the answer is 16.

For the second test case:

Ninja will pick the slice having weight 6, so his friends will pick the slices having weights 5 and 1. After that Ninja will pick the slice with weight 4 and his friends will pick 3 and 2.
Ninja’s sum will be 10 which is the maximum.
Hence,the answer is 10.
Sample Input 2:
2
9
6 5 8 4 9 2 3 1 9 
6
6 9 7 2 10 5
Sample Output 2:
26
19
Hint

Break the problem into smaller subproblems.

Approaches (3)
Recursion

In this problem, we can observe a pattern that Ninja can’t take any adjacent slices and the array is a circular array, so if Ninja takes the first slice he can’t take the last slice and vise-versa.

So,we will define a recursive function REC(‘ARR’,N,M) which will return the maximum sum if we choose M slices from first N slices of ‘ARR’.

The value of REC(‘ARR’,N,M) will be maximum of REC(‘ARR’,N-1,M) {Not taking the Nth slice} and ARR[N-1] + REC(‘ARR’,N-2,M-1) {Taking the Nth slice.}

But as we can’t first and last element together,we will create two arrays ARR1(from index 0 to N-2) and ‘ARR2’(from index 1 to index N-1.)

We will run the REC() function for both the array and return the maximum.  

 

Algorithm:

 

  • Defining REC(’ARR’,’N’,’M’) function:
    • If ‘N’ is less than or equal to 0,no element in the array.
      • Return 0.
    • If ‘M’ is equal to 0,all slices are taken.
      • Return 0.
    • Return maximum of REC(ARR,N-1,M) and (REC(ARR,N-2,M-1) + ARR[N-1]).
  • Set ‘ANS’ as 0.
  • Declare two arrays ‘ARR1’ and ‘ARR2’.
  • Copy ARR[0..(N-2)] to ‘ARR1’.
  • Copy ARR[1..(N-1)] to ‘ARR2’.
  • Set M as N/3 as Ninja can take utmost N/3 slices.
  • Set ‘ANS’ as maximum of ‘ANS’ and REC(‘ARR1’,N-1,M).
  • Set ‘ANS’ as maximum of ‘ANS’ and REC(‘ARR2’,N-1,M).
  • Return ‘ANS’.
Time Complexity

O(2^N), where ‘N’ is the number of elements in array ‘ARR’.

 

In this approach, we use recursive functions and each recursive function is making 2 more function calls. So the total number of function calls will be 2^N. Hence, the overall time complexity is O(2^N).

Space Complexity

O(N^2), where ‘N’ is the number of elements in array ‘ARR’.

 

In this approach, we are using recursive functions, so in worst case, a total space of N*M will be used for the memory stack for each state and the value of M is  N/3. Hence, the overall space complexity is O(N*N).

Code Solution
(100% EXP penalty)
Pizza Sharing
Full screen
Console