Ninja's Trip

Moderate
0/80
56 upvotes
Asked in companies
AmazonAmazon

Problem statement

Ninja is willing to take some time off from his training and planning a year-long tour. You are given a DAYS array consisting of ‘N’ days when Ninjas will be traveling during the year. Each Day is an integer between 1 to 365 (both inclusive). Train tickets are sold in three different ways: 
A 1-day pass is sold for 'COST'[0] coins,
A 7-day pass is sold for 'COST'[1] coins, and
A 30-day  pass is sold for 'COST'[2] coins.
The passes allow for many days of consecutive travel.
Your task is to help the Ninja to find the minimum number of coins required to complete his tour. For example, 
If Ninja gets a 7-day pass on day 2, then he can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.
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 days Ninja wants to travel.
The second line of each test case has ‘N’  sorted integers corresponding to the DAYS.
The third line of each test case contains a 'COST' array having three integers corresponding to the 'COST' of a 1-day pass, a 7-day pass, and a 30-day pass.
Output Format: 
For each test case, print a single integer corresponding to the minimum number of coins required to travel every day in the given list of days

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 <= 365
1 <= DAYS[i] <= 365

Time Limit: 1 sec
Sample Input 1:
2
2 
2 5
1 4 25    
7
1 3 4 5 7 8 10
2 7 20
Sample Output 1:
2
11
Explanation For sample input 1:
For the first test case, 
On Day 2, Ninja will buy a 1-day pass with 1 coin.
On Day 5, Ninja will buy a 1-day pass with 1 coin.
In total, Ninja will spend 2 coins. Hence the answer is 2.

For the second test case,
On Day 1, Ninja will buy a 1-day pass with 2 coins.
On Day 3, Ninja will buy a 7-day pass with 7 coins valid for days 3,4,5...9.
On Day 10, Ninja will buy a 1-day pass with 2 coins.
In total, Ninja will spend 11 coins. Hence the answer is 11.
Sample Input 2:
2
6
1 4 6 7 8 20
2 7 15
12
1 2 3 4 5 6 7 8 9 10 30 31
2 7 15
Sample Output 2:
11
17
Hint

Try to recur every day and try to buy every possible pass on that day.

Approaches (4)
Recursion

In this approach, we will traverse each day recursively and if we are not traveling on that day, we will wait to buy a pass. Otherwise, we have three choices to buy a pass ( a 1-day, 7-day, or 30-day pass).

 

We can express those choices as recursion and use dynamic programming. Let's say 'DP'[i] is the 'COST' to fulfill your travel plan from day ‘i’ to the end of the plan. Then, if you have to travel today, your 'COST' is:

'DP'[i] = min('DP'[i+1] + 'COST'[0], 'DP'[i+7] + 'COST'[1], 'DP'[i+30] + 'COST'[2])

And if ith day is not a 'TRAVELDAY':

'DP'[i] = 'DP'[i+1]

We will an array 'TRAVELDAY' to check whether the ith day is travel day or not. 

 

Algorithm:

  • We will define a recursive function helper(i, 'COST', 'TRAVELDAY') that will return the minimum 'COST' of the trip from the ith day to the end of the trip.
  • Defining helper'(i, 'COST', 'TRAVELDAY', 'MEMO'):
    • If i is greater than 365 (Base case of recursion), return 0.
    • If 'TRAVELDAY'[i] is equal to 0, that means Ninja is not traveling on that day
      • Return  helper(i+1,'COST','TRAVELDAY') (Not buying any pass)
    • Otherwise
      • Return the minimum of helper(i+1,'COST','TRAVELDAY')+'COST'[0], helper(i+7,'COST','TRAVELDAY')+'COST'[1], helper(i+30,'COST','TRAVELDAY')+'COST'[2]. (Recursively calling for all 3 choices).
  • Declare two arrays of size 366 'TRAVELDAY'.
  • Initialize all the values of 'TRAVELDAY' with 0.
  • For each day in ‘DAYS’ array:
    • Set 'TRAVELDAY'[day] as 1.
  • Declare a variable ‘ANS’ to store the answer.
  • Set ‘ANS’ as helper(1,'COST','TRAVELDAY').
  • Return ‘ANS’.
Time Complexity

O(3^N), where N is the number of days in a Ninja's Tour.

 

For all days in TRAVELDAY, we are calling the recursion function 3 times. Hence the overall time complexity is O(3^N).

Space Complexity

O(1).

 

We are using an array of size 366 to store 'TRAVELDAY'. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja's Trip
Full screen
Console