# Tickets Needed To get Minimum cost

• You want to buy public transport tickets for the upcoming month.
You know exactly the days on which you will be travelling.
The month has 30 days and there are three types of ticket:

1-day ticket, costs 2, valid for one day;
7-day ticket, costs 7, valid for seven consecutive days (e.g. if the first valid day is X, then the last valid day is X+6);
30-day ticket, costs 25, valid for all thirty days of the month.
You want to pay as little as possible.

You are given a sorted (in increasing order) array A of dates when you will be travelling. For example, given:

A[0] = 1
A[1] = 2
A[2] = 4
A[3] = 5
A[4] = 7
A[5] = 29
A[6] = 30

You can buy one 7-day ticket and two 1-day tickets. The two 1-day tickets should be used on days 29 and 30.
The 7-day ticket should be used on the first seven days of the month.
The total cost is 11 and there is no possible way of paying less.

Write a function:

class Solution { public int solution(int[] a); }

that, given a zero-indexed array A consisting of N integers that specifies days on which you will be traveling, returns the minimum amount of money that you have to spend on tickets for the month.

For example, given the above data, the function should return 11, as explained above.

Assume that:
-N is an integer within the range [0..30];

-each element of array A is an integer within the range [1..30];

-array A is sorted in increasing order;

-the elements of A are all distinct.

• int Solution(int[] A){
if (A.Length >= 25) //25+ days = 25
return 25;

``````	if (A.Length <= 3) { // 3 days * 2 = 6
return (A.Length * 2);
}

int index = 0;
int daysCount = 0;
int finalAmount = 0;
int seventh = 0;
int totalCount = 0;
bool isJLoopFinish = false;

for (int i = 0; i < A.Length; i++) {

if (isJLoopFinish == true) {
seventh++;
break;
}

daysCount = 0;
index = A [i] + 7;
totalCount++;

for (int j = i+1; j < A.Length ; j++) {
if ((daysCount >= 3)  && (A [j] < index) && (j == (A.Length-1))) {
Debug.LogError ("j loop finiasg");
isJLoopFinish = true;
}

if (A [j] < index) {
daysCount++;
} else {
if (daysCount > 3) {
seventh++;
daysCount = 0;
i = j-1;
} else {
daysCount = 0;
}
break;
}
}
}

totalCount = totalCount - seventh;
finalAmount = (totalCount * 2) + (seventh * 7);

if (finalAmount > 25) {
finalAmount = 25;
}
return finalAmount;
}``````

• ``````int solution(std::vector <int> &v)
{

if (v.size() <= 3) return v.size() * 2;
if (v.size() >= 23) return 25;

int stInd = 0;
int vdind = 0;

std::vector <std::deque <int>> vdecs = { { v[0] } };

for (size_t i = 1; i < v.size(); ++i)
{
if (vdecs[vdind].size() >= 3 &&
vdecs[vdind].size() <= 6 &&
v[i] - v[stInd] > 6 &&
i + 1 < v.size() &&
v[i + 1] - v[stInd + 1] <= 6
)
{
vdecs[vdind].pop_front();
stInd++;
vdecs[vdind].push_back(v[i]);
continue;
}

if (v[i] - v[stInd] <= 6) {

vdecs[vdind].push_back(v[i]);
}
else {
vdecs.push_back({});
vdind++;
vdecs[vdind].push_back(v[i]);
stInd = i;
}

}

int result = 0;
int decCnt = 0;
for (auto i = vdecs.cbegin(); i != vdecs.cend(); ++i)
{
if (i->size() >= 4) {
result += 7;
decCnt += i->size();
}

}

result += (v.size() - decCnt) * 2;

}

``````

• ``````public int solutionRajesh(int days[]) {
int n = days.length;
int cost[] = new int[n];
int oneDayCost = 2, sevenDayCost = 7, thirtyDayCost = 25;
cost[0] = oneDayCost;
for (int i = 1; i < n; i++) {
cost[i] = cost[i - 1] + oneDayCost;
int diff = days[i] - days[0];
if (i >= 12) {
int pass30Cost = ((diff + 1) / 30) * thirtyDayCost;
int pass30RemainsCost1DayPass = ((diff + 1) % 30) * oneDayCost;
int pass30RemainsCost7DayPass = ((diff + 1) % 30) / 7 * sevenDayCost;
int pass30RemainsCost7DayPassRemain1DayPass = ((diff + 1) % 30) % 7 * oneDayCost;
int pass30RemainsCost7DayTot = pass30RemainsCost7DayPass
+ (pass30RemainsCost7DayPassRemain1DayPass < sevenDayCost ? pass30RemainsCost7DayPassRemain1DayPass
: sevenDayCost);
int pass30orPass7 = (pass30RemainsCost7DayTot < pass30RemainsCost1DayPass ? pass30RemainsCost7DayTot
: pass30RemainsCost1DayPass);
int pass30CostFinal = pass30Cost + (pass30orPass7 < thirtyDayCost ? pass30orPass7 : thirtyDayCost);
cost[i] = cost[i] > pass30CostFinal ? pass30CostFinal : cost[i];
} else if (i >= 3) {
int pass7Cost = ((diff + 1) / 7) * sevenDayCost;
int pass7RemainDaysCost = (((diff + 1) % 7) * oneDayCost) < sevenDayCost ? (((diff + 1) % 7) * oneDayCost)
: sevenDayCost;
pass7Cost += pass7RemainDaysCost;
cost[i] = cost[i] > pass7Cost ? pass7Cost : cost[i];
}
}
System.out.println("Total Cost " + cost[n - 1]);
return cost[n - 1];
}
``````

• @muthaiah

Hi muthaiah! I can't understand why you check the i if it is more or equal to 3 and 12?

Could you please explain it to me a little more?

• //============================================================================
// Name : Tickets.cpp
// Author : Moaz
// Version :
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <math.h>
#include <string.h>
using namespace std;

vector<int> days;
int mem[31];
int choice(int idx) {
if (idx >= days.size())
return 0;
if (mem[idx] != -1)
return mem[idx];

``````int res = choice(idx + 1) + 2;
for (int j = idx; j < days.size() - 1; j++) {
if (days[j + 1] - days[j] > 7) {
res = min(res, choice(j + 1) + 7);
break;
}
}
return mem[idx] = res;
``````

}
int main() {

``````int arr[] = { 1, 2, 4, 5, 7, 29, 30 };
days = vector<int>(arr, arr + 7);
memset(mem, -1, sizeof(mem));
cout << min(25, choice(0));
return 0;
``````

}

• Here in python, i pasted image screenshot coz the web editor does not accept python syntax:

• @eigenfield
This solution fails for the following scenario: [1,2,4,5,7,8,9,10,11,12,29,30]

Program output: 19

Days are divided as follows: 1,2,(4,5,7,8,9,10),11,12,29,30

Expected output: 18

Days should be divided as follows: (1,2,4,5,7),(8,9,10,11,12),29,30

• ``````public class Solution {
public static int solution(int[] A) {
if(A.length >= 23) {
return 25;
} else if(A.length <= 3) {
return 2 * A.length;
}
int ans = Math.min(solve(A, 1, A[0]+6)+7, solve(A, 1, 0)+2);
return Math.min(ans, 25);
}

public static int solve(int[] A, int index, int max) {
if(index >= A.length) {
return 0;
}
if(A[index] <= max) {
return solve(A, index+1, max);
} else {
return(Math.min(solve(A, index+1, A[index]+6)+7, solve(A, index+1, 0)+2));
}
}
``````

• dp for this problem:

``````function calMinCosts(arr){
if(!arr || arr.length===0)
return 0;

var len = arr.length;
var costsOfDateArr = Array.apply(null,{length:arr[len-1]+1}).map(()=>0);

var price1=2,price2=7,price3=25;
var days=7;

var index=0,n=costsOfDateArr.length;
for(var i=1;i<n;i++){
if(i===arr[index]){
if(i>=days+1){
costsOfDateArr[i] = Math.min(costsOfDateArr[i-days-1]+price2, costsOfDateArr[i-1]+price1);
}else{
costsOfDateArr[i] = Math.min(costsOfDateArr[0]+price2, costsOfDateArr[i-1]+price1);
}
index+=1;
}else{
costsOfDateArr[i] = costsOfDateArr[i-1];
}
}

return Math.min(price3,costsOfDateArr[n-1]);
}

``````

• public class MinTicketFare {
static final int MONTH_PASS = 25;
static final int WEEK_PASS = 7;
static final int DAY_PASS = 2;

``````public static void main(String[] args) {
int[] dates = { 1, 2, 4, 5, 7, 9, 29, 30 };
int cost = findMinCost(dates);
System.out.println("Min cost =" + cost);
}

private static int findMinCost(int[] dates) {
int[] dp = new int[dates.length + 1];

dp[1] = DAY_PASS;
for (int i = 2; i < dp.length; i++) {
dp[i] = dp[i - 1] + 2;
}

for (int i = 1; i < dp.length; i++) {
// at ith day, we can either take DAY Pass or include it in our
// WEEK_PASS range.
int a = Math.min(dp[i - 1] + DAY_PASS, checkForWeekPass(dates, dp, i));
dp[i] = Math.min(dp[i], a);
// System.out.println("i=" + i + " , dp[i] = "+dp[i]+ " , dates[i] =
// "+dates[i-1] +" , checkForWeekPass(dp, i) = " + a);
}
return Math.min(MONTH_PASS, dp[dp.length - 1]);
}

private static int checkForWeekPass(int[] dates, int[] dp, int i) {
int offset = 0;
int index = getLastReachableDate(dates, i - 1);
offset = dp[index + 1];
return WEEK_PASS + offset;
}

private static int getLastReachableDate(int[] dates, int index) {
int currentDate = dates[index];
while (index > -1 && (currentDate - dates[index]) < 7) {
index--;
}
return index;
}
``````

}

• public class Solution {
static ArrayList<Double> costOption=new ArrayList<Double>();
static double []costArray=new double[13];
static int days[] ={1,2,3,4,5,6,7,8,9,10};

``````static double Solution(){
int []paymentPlan={2,7,30};

if(days.length>=23){
return 25;
}
else if(days.length<=3){
return days.length*2;
}

else{
for (int day : days) {
costOption.clear();
costArray[day-1]=Collections.min(costOption);
}
}
return costArray[days.length-1];
}

public static double calculateDailyPlan(int day){
if(day<=1){
return 2;
}
else{
return 2+costArray[day-1-(1)];
}
}

public static double calculateWeeklyPlan(int day){
if(day<=7){
return 7;
}
else{
return 7+costArray[day-1-(7)];
}
}
public static double calculateMonthlyPlan(int day){
if(day<=30){
return 25;
}
else{
return 25+costArray[day-1-(30)];
}
}
public static void main(String args[])
{
System.out.println(Solution());
}
``````

}

• My dp solution(Please point out if there is any error):

``````public class HelloWorld{

public static void main(String []args){
int[] trvl = {1,2,4,5,7,29,30};
int[] dp = new int[31];
dp[0]=0;
int ct=0;
for(int i=1; i<=30; i++){
if(ct==trvl.length){
dp[30]=dp[i-1];
break;
}
else{
if(trvl[ct]==i){
ct++;
int r=0;
if(i-7<0){
r=7;
}
else{
r = dp[i-7]+7;
}
if(i-1<0){
r=(int)Math.min(r,2);
}
else{
r=(int)Math.min(r,dp[i-1]+2);
}
if(i-30<0){
r=(int)Math.min(r,25);
}
else{
r=(int)Math.min(r,dp[i-30]+25);
}
dp[i]=r;
}
else{
dp[i]=dp[i-1];
}
}
}
System.out.println(dp[30]);
}
}
``````

• Code in C++
Not the most optimized version but works.

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> &A)
{
auto M = A[A.size() - 1];
auto sizeof_min_cost_vector  = M + 1;

vector<bool> dayTravelled (sizeof_min_cost_vector);

for(auto day: A)
{
dayTravelled[day] = true;
}

vector<int> minCostVector (sizeof_min_cost_vector);

// base case: cost for travelling on day 0
minCostVector[0] = 0;

// here i  = days, you travel from days 1 to sizeof_min_cost_vector - 1
for(int i = 1; i < sizeof_min_cost_vector; i++)
{
if(!dayTravelled[i]){
minCostVector[i] = minCostVector[i-1];
continue;
}

int minCost;

// Case 1: Take daily pass
// Add \$2 to the cost of previous day
minCost = minCostVector[i-1]  + 2;

// Case 2: Take a 7 day pass
// cost = cost from day [i-7] + 7 to day [i-1] + 7
// because on each of these days you can get the ticket
// the for loop is because you can buy the pass from day (i-7) all the way to day (i-1)
for(int d = max(0,i-7); d<= i-1; d++)
{
minCost = min(minCost, minCostVector[d] + 7);
}

// Case 3: Take a 30 day pass
// cost =  you can buy pass all the way from day [i-30] to day [i-1]
// hence cost  = day[i - x] + 25, where x goes from 30 to 1
for (int d = max(0, i-30); d <= i-1; d++)
{
minCost = min(minCost, minCostVector[d] + 25);
}

minCostVector[i] = minCost;
}

return minCostVector[sizeof_min_cost_vector - 1];
}

int main()
{

vector<int> A {1, 3, 5, 8, 9, 10};
cout << solution(A) << endl;

return 0;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.