Mario And His Princess

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote
Asked in company
Walmart

Problem statement

Mario is going to meet his princess who is in a castle and there is a path from Mario's current location to the castle. On the path to the castle, there are dragons who do not burn instead they give DIAMOND. Mario will receive DIAMOND if and only if he didn't take any diamond from the dragon standing directly before the current dragon. In general he can not take DIAMOND from two successive dragons, if he does so then the dragons will burn him.

You are in charge of controlling Mario. There are ‘N’ dragons, you are given an array ‘DIAMOND’ of length ‘N’ where DIAMOND[i] denotes the number of DIAMOND the i-th dragon will give.

The task is to collect the maximum DIAMOND for the princess. You can not take the diamonds from two successive dragons.

All the indexing in the explanation of examples and test cases is 1-based but in the input array, 0-based indexing is used.

Example:

Input: 'N' = 5, 'DIAMOND' = [1, 2, 3, 4, 5]

Output: 9

Mario can take the following combinations of DIAMOND without getting burn:-
1, 3, 5 = 1 + 3 + 5 = 9.
1, 4 = 1 + 4 = 5
1, 5 = 1+5 = 6
2, 4 = 2+4 = 6
2, 5 = 2+5 = 7
3, 5 = 3+5 = 8

Also, he can take all the DIAMOND uniquely as well means he takes DIAMOND from the single dragon but the max DIAMOND he can get is 9.   
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

For each test case, the first line will contain a single integer 'N', the size of the array 'DIAMOND' 

The second line of each test case will contain ‘N’ integers representing the array elements.

Output format :

For each test case, print the maximum DIAMOND Mario can get.

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^5
1 <= DIAMOND[i] <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
5
1 2 3 4 5
5
1 1 1 1 1
Sample Output 1 :
9
3
Explanation Of Sample Input 1 :
For the first case:
Mario can take the following combinations of DIAMOND without getting burn:-
1, 3, 5 = 1+3+5 = 9.
1, 4 = 1+4 = 5
1, 5 = 1+5 = 6
2, 4 = 2+4 = 6
2, 5 = 2+5 = 7
3, 5 = 3+5 = 8
Also, he can take all the DIAMOND uniquely as well means he takes DIAMOND from the single dragon but the max DIAMOND he can get is 9.  

For the second case:
Anyhow Mario takes the diamond he can at most 3 DIAMOND by taking DIAMOND from 1, 3, and 5.
Sample Input 2 :
2
2 
1 2
4 
1 2 3 4
Sample Output 2 :
2
6
Hint

Can you think of some recursive solution?

Approaches (3)
Recursion

There are ‘N’ dragons on the road and for each dragon, we have two choices either we take the diamond from him or we don’t take the diamond from him. We can not take DIAMOND from two successive dragons so have to make sure of that as well.


 

Initially, we have 0 DIAMOND and for each ‘i’ from 0 to ‘N’-1 (0-based indexing), we can take DIAMOND from the current dragon if we haven’t taken DIAMOND from the direct previous dragon of the current dragon if there are any, and for that, we will make a flag which we will make false when we take the DIAMOND and we take diamond if the flag is true and if we don’t take the diamond than make the flag true and call for the next index and return the max of the cases where we took the DIAMOND from the current dragon and we didn’t take the diamond from the current dragons.


The Steps are as follows:-

maxDiamondRec( i:int, flag:bool, DIAMOND:[], currSum:[] ):

  1. Create a variable denoting size of the array.
  2. If we are out the index of the array. Return currSum.
  3. Check the answer if we don't take the current element.
  4. As we are not taking the current element so we can take the next element so make the flag value high Store it in x.
  5. Create another variable y with an initial value equal to zero.
  6. Check if we can take the diamond from the current dragon. If Yes then take the diamond from the current dragon and set the flag to false as we can't take the diamond from the Next successive dragon.
  7. Return the max of x,y.

diamondForPrincess( diamond )

  1. Call the maxDiamondRec function with current index(i) = 0, flag = true, currSum = 0.
Time Complexity

O( 2 ^ N ), Where ‘N’ is the number of dragons 'DIAMOND'.



For each dragon, we either take diamonds from him or don’t take diamonds from him so we have 2 choices for each dragon and there are ‘N’ dragons. This will give TLE.

Hence Time complexity is O( 2^N ).

Space Complexity

O( 1 ).

 

We are not using any extra space.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Mario And His Princess
Full screen
Console