Bird and maximum fruit-gathering

Easy
0/40
Average time to solve is 20m
1 upvote
Asked in company
Facebook

Problem statement

There are ‘N’ trees in a circle. Each tree has a fruit value associated with it. A ninja bird eyeing the fruits on the tree is blazingly fast. It can sit on a tree for 0.5 sec to gather all the fruits present on the tree no matter the number of fruits present in the tree and then the ninja bird can move to a neighboring tree. It takes the ninja bird 0.5 seconds to move from one tree to another. Once all the fruits are picked from a particular tree, she can’t pick any more fruits from that tree. The maximum number of fruits she can gather is infinite.

You are given N and M (the total number of seconds the ninja bird has), and the fruit values of the trees. Your task is to maximize the total fruit value that the ninja bird can gather. The bird can start from any tree.

Note 
All trees are in a circle.
For Example: 
Input: N = 7 M = 3
ARR[] = { 2, 1, 3, 5, 0, 1, 4 }

Output: 9

Explanation: 
She can start from tree 1 and move to tree 2 and then to tree 3.
Hence, total number of gathered fruits = 1 + 3 + 5 = 9.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains a single integer ‘T’ denoting the number of test cases for the problem.

The first line of each test case in the input contains two space-separated integers ‘N’ and ‘M’ denoting the number of trees and the seconds given to collect the fruits from the trees.

And the second line contains 'N' single space-separated integers, denoting the fruits on each tree.
Output Format: 
For each test case, print a single line containing a single integer denoting the maximum number of fruits the ninja bird can gather in the given amount of time.

The output of each test case will be printed 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 <= 100
1 <= M <= 5000
1 <= N <= 5000
1 <= ARR[i] <= 5000

Time Limit: 1 sec.
Sample Input 1 :
2
6 2
1 6 2 5 3 4
7 3
2 1 3 5 0 1 4
Sample Output 1:
8
9
Explanation for Sample 1:
She can start from tree 1 and move to tree 2. In this case, she will gather 6 + 2 = 8 fruits. She can also start from tree 3 and move to tree 4. In this case, too, she will gather 5 + 3 = 8 fruits. Therefore the answer here is 8.

She can start from tree 1 and move to tree 2 and then to tree 3. Hence, the total number of gathered fruits = 1 + 3 + 5 = 9.
Sample Input 2 :
1
8 3
2 3 4 1 2 1 5 3
Sample Output 2 :
10
Hint

Iterate over the trees from the first tree and keep checking whether the maximum sum is obtained or not.

Approaches (2)
Brute Force

We will iterate through the trees with the help of a nested loop. Where we will further loop for the given number of seconds ‘m’, checking for every sum that we obtain is the maximum sum or not and update the sum on each iteration if it is maximum.

 

The algorithm will be-

  1. We will run a loop from the starting tree of the given list.
  2. Now from every tree, we will run a loop and traverse the remaining trees and sum the fruits collected and now check if there exists a sum with a bigger value than our current sum.
    1. We will maintain a variable ‘max_so_far’ for finding the maximum sum that we have gotten initialised by 0.
    2. Now for each tree that we traverse, we will keep adding the fruits in the trees for the given number of seconds after which we will check if the ‘max_so_far’ is greater than the ‘max_sum’ that we want and update the ‘max_sum’ if ‘max_so_far’ is greater than ‘max_sum’.
  3. We finally return the ‘max_sum’.
Time Complexity

O(N ^ 2), where ‘N’ denotes the number of trees.

 

Since we are visiting all the trees given with the help of two nested loops. Therefore the time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

Since constant space is used.

Code Solution
(100% EXP penalty)
Bird and maximum fruit-gathering
Full screen
Console