Practice Projects

Minimum Cost For Tickets Javascript C++

Problem Statement

Aapne next year ke liye kuch train journeys plan ki hain, aur ek integer array days diya gaya hai jo wahin days hai jab aap travel karoge. Yeh days 1 se lekar 365, saal ke kisi bhi din ko represent kar sakte hain.Train tickets teen tareeke se milte hain:
Ek 1-day pass jo costs[0] dollars ka hota hai.
Ek 7-day pass jo costs[1] dollars ka hota hai.
Ek 30-day pass jo costs[2] dollars ka hota hai.Yeh passes utne hi consecutive days ka travel cover karte hain jitne unka tenure hai. Jaise agar aap 7-day pass day 2 ko lete ho, toh aap 2 se lekar 8 tak, 7 din travel kar sakte ho.Aapko pata karna hai ki minimum kitne dollars aapko spend karne honge, taaki aap apni list of days mein har din travel kar sako.
Example 1: Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11 Explanation: Yahan ek tariqa hai passton ko kharidne ka taaki aap apne travel plan cover kar sako:Day 1 ko, aapne 1-day pass kharida jo costs[0] = $2 ka tha. Yeh day 1 ko cover kar raha hai. Day 3 ko, aapne 7-day pass kharida jo costs[1] = $7 ka tha. Yeh day 3, 4, …, 9 din cover kar raha tha. Day 20 ko, aapne 1-day pass kharida jo costs[0] = $2 ka tha. Yeh day 20 ko cover kar raha tha. In total, aapne $11 kharch kiye aur apne sabhi travel days cover kar liye.Example 2: Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17 Explanation: Yahan ek tariqa hai passton ko kharidne ka taaki aap apne travel plan cover kar sako:Day 1 ko, aapne 30-day pass kharida jo costs[2] = $15 ka tha. Yeh day 1 se lekar 30 tak cover kar raha tha. Day 31 ko, aapne 1-day pass kharida jo costs[0] = $2 ka tha. Yeh day 31 ko cover kar raha tha. In total, aapne $17 kharch kiye aur apne sabhi travel days cover kar liye.
Constraints:
1 <= days.length<= 365
1 <= days[i] <= 365 days strictly increasing order mein hone chahiye.
costs.length3 hona chahiye. 1 <= costs[i] <= 1000
Practice Projects

Minimum Cost For Tickets Javascript C++

Train travel ka minimum cost nikaalne ke liye, jab specific travel days aur ticket costs diye gaye hain, hum ek dynamic programming (DP) approach use kar sakte hain. Is idea ko implement karne ke liye, hum ek DP array maintain karte hain jahan har entry represent karegi minimum cost jo hume chahiye ek specific day tak travel cover karne ke liye.

Intuition

Dynamic Programming Array: Ek DP array banayein dp jahan dp[i] represent karega minimum cost jo travel karne ke liye chahiye day i tak.Initialization: DP array ka size 366 set kariye (days 1 se 365 tak cover karne ke liye) aur dp[0] = 0 set karein (day 0 pe cost nahi lagti).Iterate Over Travel Days: Har travel day ke liye days array mein, minimum cost calculate karein based on three types of passes:1-day pass: Iski cost hogi 1-day pass ki cost plus previous day tak travel ki cost,7-day pass: Iski cost hogi 7-day pass ki cost plus woh cost jo travel day se 7 din pehle ka din cover karta hai (ya 0 agar woh day 1 se pehle chala jaye),30-day pass: Iski cost hogi 30-day pass ki cost plus woh cost jo travel day se 30 din pehle ka din cover karta hai (ya 0 agar woh day 1 se pehle chala jaye).Update the DP Array: Har din ke liye days array mein, DP array ko update karein minimum cost se jo teen options mein se calculate hui hai.Return the Result: Result dp[365] mein milega, jo minimum cost dega sab travel days ko cover karne ke liye.

Approach
  • Time Complexity:

    • O(365 + d) hai, jahan d travel days ka number hai. Loop total 365 days ke liye chalega aur hum har travel day ko check karenge.

    Space Complexity:

    • O(1) hai DP array ke liye, kyunki iska size fixed hai 366.

Solution

				
					var mincostTickets = function(days, costs) {
    const dp = new Array(366).fill(0); // DP array for days 0 to 365
    const travelDays = new Set(days); // Set for quick lookup of travel days

    // Har saal ke din ko iterate karo
    for (let i = 1; i <= 365; i++) {
        if (travelDays.has(i)) {
            // Har tarah ki ticket ke liye cost calculate karo
            const cost1 = dp[i - 1] + costs[0]; // 1-day pass
            const cost7 = dp[Math.max(0, i - 7)] + costs[1]; // 7-day pass
            const cost30 = dp[Math.max(0, i - 30)] + costs[2]; // 30-day pass
            
            // Teen options mein se minimum cost lo
            dp[i] = Math.min(cost1, Math.min(cost7, cost30));
        } else {
            // Agar travel day nahi hai, toh pehle ka cost carry forward karo
            dp[i] = dp[i - 1];
        }
    }

    // Answer minimum cost hoga saare travel days ko cover karne ke liye
    return dp[365];
};

  1. const dp = new Array(366).fill(0); – Yahan hum ek DP array bana rahe hain jo 0 se 365 days tak sab kuch 0 se fill karta hai.

  2. const travelDays = new Set(days); – Hum ek set bana rahe hain travel days ka quick lookup karne ke liye.

  3. For Loop (for (let i = 1; i <= 365; i++)):

    • Har saal ke din ko 1 se 365 tak traverse kar raha hai.

    • if (travelDays.has(i)) – Check kar raha hai ki kya current day travel day hai.

      • Agar travel day hai, to teen tarah ki passes (1-day, 7-day, 30-day pass) ke liye cost calculate karta hai:

        1. 1-day pass: dp[i - 1] + costs[0]

        2. 7-day pass: dp[Math.max(0, i - 7)] + costs[1]

        3. 30-day pass: dp[Math.max(0, i - 30)] + costs[2]

      • In teen options mein se jo minimum cost hoga, usse dp[i] update karo.

    • Agar current day travel day nahi hai, to previous day ka cost carry forward kar do: dp[i] = dp[i - 1]

  4. Return Statement:

    • return dp[365]; – Yeh minimum cost return karega sab travel days ko cover karne ke liye.

Yeh code minimum cost calculate karne ke liye DP approach use karta hai aur efficiently travel days ko cover karta hai.

Solution

				
					#include <vector>
#include <algorithm>

class Solution {
public:
    int mincostTickets(std::vector<int>& days, std::vector<int>& costs) {
        int n = days.size();
        std::vector<int> dp(366, 0); // DP array for days 0 to 365

        // Har saal ke din ko traverse karo
        for (int i = 1; i <= 365; i++) {
            // Agar travel day nahi hai, toh pehle ka cost carry forward karo
            if (std::find(days.begin(), days.end(), i) == days.end()) {
                dp[i] = dp[i - 1];
            } else {
                // Har type ki ticket ke liye cost calculate karo
                int cost1 = dp[i - 1] + costs[0]; // 1-day pass
                int cost7 = dp[std::max(0, i - 7)] + costs[1]; // 7-day pass
                int cost30 = dp[std::max(0, i - 30)] + costs[2]; // 30-day pass
                
                // Teen options mein se minimum cost lo
                dp[i] = std::min(cost1, std::min(cost7, cost30));
            }
        }

        // Answer minimum cost hoga sab travel days ko cover karne ke liye
        return dp[365];
    }
};

  • #include <vector> aur #include <algorithm> necessary header files include kar rahe hain jo aapko vector aur algorithm functionalities provide karte hain.

  • class Solution define kar rahe hain jo mincostTickets function implement karega.

  • mincostTickets function ko days aur costs vector ke references mil rahe hain.

  • dp array initialize kar rahe hain size 366 ke saath, 0 se 365 days cover karne ke liye.

  • For loop 1 se 365 tak iterate karta hai:

    • Agar i travel day nahi hai toh dp[i] ko previous day ke cost se fill karte hain.

    • Agar i travel day hai toh teen tarikon se cost calculate karte hain: 1-day, 7-day aur 30-day pass ke basis pe.

    • Minimum cost ko dp[i] mein save karte hain.

  • Function ke end mein dp[365] return karte hain jo minimum cost hai sab travel days cover karne ke liye.

channels4_banner