<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Surendra Tholiya on Medium]]></title>
        <description><![CDATA[Stories by Surendra Tholiya on Medium]]></description>
        <link>https://medium.com/@suren015?source=rss-9aa46c28d293------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*mhLOepUYnJvQ78FSpmvNIw.jpeg</url>
            <title>Stories by Surendra Tholiya on Medium</title>
            <link>https://medium.com/@suren015?source=rss-9aa46c28d293------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 16:36:47 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@suren015/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Integrate Google Test, Google Mock and Boost Library with an Existing Visual Studio Solution]]></title>
            <link>https://suren015.medium.com/integrate-google-test-google-mock-and-boost-library-with-an-existing-visual-studio-solution-b216f663c4ee?source=rss-9aa46c28d293------2</link>
            <guid isPermaLink="false">https://medium.com/p/b216f663c4ee</guid>
            <category><![CDATA[integration]]></category>
            <category><![CDATA[google-test]]></category>
            <category><![CDATA[bobst-library]]></category>
            <category><![CDATA[visual-studio-code]]></category>
            <category><![CDATA[google-mock]]></category>
            <dc:creator><![CDATA[Surendra Tholiya]]></dc:creator>
            <pubDate>Tue, 29 Apr 2025 04:10:05 GMT</pubDate>
            <atom:updated>2025-04-29T04:13:18.956Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>💻💻<em> Steps to Integrate Google Mock with an Existing Visual Studio Solution</em></strong></p><ol><li><strong>Open the Existing Solution<br> </strong>Launch the .sln file in Visual Studio.</li><li><strong>Build the Solution<br> </strong>Perform a build to ensure the existing project compiles without errors before adding tests.</li><li><strong>Add a Google Test Project<br></strong>Right-click on the solution and select <strong>Add &gt; New Project</strong>.<br><strong>Search for Google Test, and select it.</strong></li><li><strong>Set the project name as:<br> &lt;YourExistingProjectName&gt;.UnitTests, then click Create.</strong></li><li><strong>Configure the Google Test Project<br> </strong>In the Test Project Configuration dialog:<br>a. Check <strong>Static Library<br></strong>b. Check<strong> Link Dynamically</strong></li><li><strong>Update Preprocessor Definitions<br></strong>a. Right-click on the <strong>Test Project</strong> &gt; <strong>Properties<br></strong>b. Navigate to<strong> Configuration Properties &gt; C/C++ &gt; Preprocessor<br></strong>c. (Optional — No Need)<strong> Edit Preprocessor Definitions and replace X64_DEBUG_CONSOLE with:<br> _SILENCE_TR1_NAMESPACE_DEPRECATION_WARNING</strong></li><li><strong>Disable Precompiled Headers<br></strong>a. Under <strong>C/C++ &gt; Precompiled Headers</strong>, set <strong>Precompiled Header</strong> to:<br> <strong>Not Using Precompiled Headers</strong></li><li><strong>Add Reference to Source Project<br></strong>a. Right-click the <strong>Test Project</strong> &gt; <strong>Add &gt; Reference<br></strong>b.<strong> Select your existing (source) project and click OK</strong></li><li><strong>Include Header Files from Source Project (Optional)<br></strong>a. Go to <strong>Properties &gt; C/C++ &gt; General &gt; Additional Include Directories<br></strong>b.<strong> Click Edit, then the folder icon, and add the path to the source project’s headers</strong></li><li><strong>Click OK and Apply</strong></li><li><strong>Set Test Project as Startup<br></strong>a. Right-click on the Test Project and choose <strong>Set as Startup Project</strong></li><li><strong>Build The Solution.</strong></li></ol><p>Error Faced — <strong>Fix ‘Not a Win32 Application’ Error<br> </strong>If you encounter this error:</p><ul><li>Make sure the <strong>Source Project</strong> is of type .lib (Static Library)</li><li>And the <strong>Test Project</strong> is of type .exe (Console Application)</li><li>To change this, go to <strong>Properties &gt; Configuration Properties &gt; General &gt; Configuration Type.</strong></li></ul><p>* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — *</p><p><strong>💻💻<em> Steps to Integrate Google Mock with an Existing Visual Studio Solution</em></strong></p><ol><li>Up to the creation of the Google Test project, no changes are needed — simply create the Google Test project.</li><li>Next, navigate to <strong>Tools</strong> &gt; <strong>NuGet Package Manager</strong> &gt; <strong>Manage NuGet Packages for Solution</strong>.<br>a. Under the <strong>Browse</strong> tab, search for <strong>google-testmock</strong> and install it <strong>only for the test project</strong>.</li><li>Then, include the gmock.h header file in your test file to proceed with mocking.</li></ol><p>* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — *</p><p><strong>💻💻<em> Steps to Integrate Boost Library with an Existing Visual Studio Solution</em></strong></p><ol><li>No changes are needed during project creation — just create any project as usual.</li><li>Go to <strong>Tools</strong> &gt; <strong>NuGet Package Manager</strong> &gt; <strong>Manage NuGet Packages for Solution</strong>.<br>a. In the <strong>Browse</strong> tab, search for and install the following packages (replace vc143 with the appropriate version for your Visual Studio installation, e.g., for Visual Studio 2022, use vc143):<br>a. boost-log-vc143<br>b. boost-thread-vc143<br>c. boost-filesystem-vc143<br>d. boost-atomic-vc143<br>e. boost-log-setup-vc143<br>f. boost-log-chrono-vc143<br>g. boost-log-system-vc143<br> Install each of these packages one by one for your main project. If you also have a test project, install them there as well.</li><li>Finally, include all the necessary Boost header files in your project source code.</li></ol><p>* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — *</p><p>If you have any issues, regarding this setup and all, you can contact me on my mail-id: “karantholiya015@gmail.com”</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b216f663c4ee" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Gas Station (Leetcode- 134)]]></title>
            <link>https://suren015.medium.com/gas-station-leetcode-134-dba63c23b6f9?source=rss-9aa46c28d293------2</link>
            <guid isPermaLink="false">https://medium.com/p/dba63c23b6f9</guid>
            <dc:creator><![CDATA[Surendra Tholiya]]></dc:creator>
            <pubDate>Thu, 19 Dec 2024 12:04:56 GMT</pubDate>
            <atom:updated>2024-12-19T12:04:56.314Z</atom:updated>
            <content:encoded><![CDATA[<p><strong><em>✍️ Problem Statement:</em></strong></p><p>There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station&#39;s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is <strong>guaranteed</strong> to be <strong>unique</strong>.</p><p><em>👉 </em><strong><em>Example 1:</em></strong></p><pre>Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]<br>Output: 3</pre><p><em>👉 </em><strong><em>Example 2:</em></strong></p><pre>Input: gas = [2,3,4], cost = [3,4,3]<br>Output: -1</pre><p><strong><em>Constraints:</em></strong></p><ul><li>n = gas.length = cost.length</li><li>1 ≤ n ≤ 10⁵</li><li>0 ≤ gas[i], cost[i] ≤ 10⁴</li></ul><p><em>❓</em><strong><em>Problem Explanation :</em></strong></p><p>We have a car with an unlimited gas tank. We are given an array of gas and an array of costs. Each index in the gas array represents the amount of gas available to fill up your car with. Each index in the cost array represents the amount of gas that will be used when travelling from this gas station to next.<br>Our goal is to determine whether it is possible to start at any of the gas stations and complete one trip around.<br>If it is, we need to return the index of that starting gas station, if no such gas station exists then we return -1.</p><p><em>⭐ </em><strong><em>Example :</em></strong></p><p><strong><em>Input: </em></strong>gas = [1, 2, 3, 4, 5] &amp; cost = [3, 4, 5, 1, 2]<strong><em> </em></strong><em><br></em><strong><em>Output</em></strong><em>: 3</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/639/1*u1MeCeV50GIgkKjBoFAcbQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Afbjw9aPteHuxp7BT4_ECw.png" /></figure><p><strong><em>Explanation: </em></strong>Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4<br>Travel to station 4. Your tank = 4–1 + 5 = 8<br>Travel to station 0. Your tank = 8–2 + 1 = 7<br>Travel to station 1. Your tank = 7–3 + 2 = 6<br>Travel to station 2. Your tank = 6–4 + 3 = 5<br>Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.</p><p><strong><em>Let’s walk towards the solution!!🚶‍♂️‍➡️🚶‍♂️‍➡️</em></strong></p><h4><strong><em>Solution: 🔥🔥</em></strong></h4><p>Let us consider the size of the given gas array and cost array to be n.</p><blockquote><strong><em>🎯 Brute Force :</em></strong></blockquote><p><em>💡💡 </em><strong><em>Intuition :</em></strong></p><p>The problem is about determining whether there exists a starting station such that we can complete the circuit once around a circular path of gas stations without running out of gas. The brute force approach is straight forward: <strong>test each station as a potential starting point</strong> to check if it’s possible to complete the journey starting from there.<br>The intuition is to simulate the journey from every station and validate whether the total fuel remains non-negative at every step. If fuel becomes negative, that station cannot be a valid starting point.</p><p><em>🚀 🚀 </em><strong><em>Approach :</em></strong></p><ol><li><strong>Testing each station as a starting point:</strong><br> → Assume that <strong>any station</strong> could potentially be a valid starting point.<br> → To check this, we try to start the journey from <strong>each station </strong>i and simulates the trip.</li><li><strong>Simulating the Trip:<br> → </strong>From the current starting station <strong>i</strong>, move to the next station in a circular manner.<br> → Calculate the <strong>net fuel</strong> after visiting each station as: <strong>totalFuel += gas[j%n] − cost[j%n]<br> → </strong>If at any point totalFuel &lt; 0, the current starting point <strong>i</strong> fails because the car cannot proceed.</li><li><strong>Stopping Conditions</strong>:<br> → <strong>Failure Case</strong>: If totalFuel becomes negative at any point during the trip, the car can&#39;t continue further, so we break the loop.<br> → <strong>Success Case</strong>: If the car completes a full circle (stopCount == n) and the remaining totalFuel &gt;= 0, then the current station i is a valid starting point.</li><li><strong>Why </strong><strong>j % n?</strong>:<br> → The % n ensures circular traversal. After reaching the last station, it wraps around to the first station.</li><li><strong>Returning the Result</strong>:<br> → If any station i passes the conditions, return i as the starting station.<br> → If no station works, return -1.</li></ol><p><em>🏃🏃 </em><strong><em>Step-by-Step Dry Run</em></strong><em>:</em></p><p><em>1. </em>Starting from Station 0:</p><pre>a. Initialize totalFuel = 0, stopCount = 0, i = 0, j = 0.<br>b. Start simulating the journey:<br>   -&gt; Visit station 0:<br>      totalFuel += gas[0] - cost[0] = 0 + 1 - 3 = -2<br>   -&gt; Fuel is negative, so station 0 fails.</pre><p><em>2. </em>Starting from Station 1:</p><pre>a. Initialize totalFuel = 0, stopCount = 0, i = 1, j = 1.<br>b. Start simulating the journey:<br>   -&gt; Visit station 1:<br>      totalFuel += gas[1] - cost[1] = 0 + 2 - 4 = -2<br>   -&gt; Fuel is negative, so station 1 fails.</pre><p><em>3. </em>Starting from Station 2:</p><pre>a. Initialize totalFuel = 0, stopCount = 0, i = 2, j = 2.<br>b. Start simulating the journey:<br>   -&gt; Visit station 2:<br>      totalFuel += gas[2] - cost[2] = 0 + 3 - 5 = -2<br>   -&gt; Fuel is negative, so station 2 fails.</pre><p><em>4. </em>Starting from Station 3:</p><pre>a. Initialize totalFuel = 0, stopCount = 0, i = 3, j = 3.<br>b. Start simulating the journey:<br>   -&gt; Visit station 3:<br>      totalFuel += gas[3] - cost[3] = 0 + 4 - 1 = 3<br>      stopCount = 1<br>   -&gt; Visit station 4:<br>      totalFuel += gas[4] - cost[4] = 3 + 5 - 2 = 6<br>      stopCount = 2<br>   -&gt; Visit station 0:<br>      totalFuel += gas[0] - cost[0] = 6 + 1 - 3 = 4<br>      stopCount = 3<br>   -&gt; Visit station 1:<br>      totalFuel += gas[1] - cost[1] = 4 + 2 - 4 = 2<br>      stopCount = 4<br>   -&gt; Visit station 2:<br>      totalFuel += gas[2] - cost[2] = 2 + 3 - 5 = 0<br>      stopCount = 5<br>c. All stations are visited, and totalFuel &gt;= 0. Station 3 is a valid starting point.</pre><p><em>4. S</em>tarting from Station 4 (Not Needed):<br>Since station 3 is a valid starting point, the algorithm terminates early.</p><p><em>🤖🤖 </em><strong><em>Codes :</em></strong></p><blockquote><strong><em>C++ Code 👩‍💻:</em></strong></blockquote><pre>#include &lt;iostream&gt;<br>#include &lt;vector&gt;<br>using namespace std;<br><br>// Function to find the starting gas station<br>int canCompleteCircuit(vector&lt;int&gt;&amp; gas, vector&lt;int&gt;&amp; cost) {<br>    // Get the size of the arrays<br>    int n = gas.size();<br>    <br>    // Loop to test each station as a potential starting point<br>    for (int i = 0; i &lt; n; i++) {<br>        // Initialize total fuel to 0<br>        int totalFuel = 0;<br>      <br>        // Track the number of stops made<br>        int stopCount = 0;<br>        <br>        // Start journey from the current station<br>        int j = i;<br><br>        // Simulate the journey<br>        while (stopCount &lt; n) {<br>            // Calculate the remaining fuel after reaching the next station<br>            totalFuel += gas[j % n] - cost[j % n];<br><br>            // If the total fuel is negative, the journey fails<br>            if (totalFuel &lt; 0) break; <br><br>            // Increment the stop count<br>            stopCount++;<br><br>            // Move to the next station<br>            j++;<br>        }<br> <br>        // If all stops are covered and fuel is non-negative, return the starting station<br>        if (stopCount == n &amp;&amp; totalFuel &gt;= 0){<br>            return i;<br>        }<br>    }<br><br>    // If no valid starting point is found, return -1<br>    return -1; <br>}<br><br>int main() {<br>    // Declare example inputs for gas and cost arrays<br>    vector&lt;int&gt; gas = {1, 2, 3, 4, 5};<br>    vector&lt;int&gt; cost = {3, 4, 5, 1, 2};<br><br>    // Find the starting gas station<br>    int result = canCompleteCircuit(gas, cost);<br><br>    // Display the result<br>    if (result != -1) {<br>        // Display the starting station if the journey is possible<br>        cout &lt;&lt; &quot;The circuit can be completed starting from gas station: &quot; &lt;&lt; result &lt;&lt; endl;<br>    } else {<br>        // Display a message if the journey is not possible<br>        cout &lt;&lt; &quot;It is not possible to complete the circuit from any gas station.&quot; &lt;&lt; endl;<br>    }<br><br>    return 0;<br>}</pre><blockquote><strong><em>Java Code 👩‍💻:</em></strong></blockquote><pre>import java.util.*;<br><br>public class GasStation {<br>    // Function to find the starting gas station<br>    public static int canCompleteCircuit(int[] gas, int[] cost) {<br>        // Number of gas stations<br>        int n = gas.length; <br><br>        // Loop to test each station as a potential starting point<br>        for (int i = 0; i &lt; n; i++) {<br>            // Initialize total fuel to 0<br>            int totalFuel = 0; <br>    <br>            // Track the number of stops made<br>            int stopCount = 0; <br><br>            // Start journey from the current station<br>            int j = i; <br><br>            // Simulate the journey<br>            while (stopCount &lt; n) {<br>                // Calculate the remaining fuel after reaching the next station<br>                totalFuel += gas[j % n] - cost[j % n];<br><br>                // If total fuel becomes negative, the journey fails<br>                if (totalFuel &lt; 0) break;<br> <br>                // Increment the stop count<br>                stopCount++; <br><br>                // Move to the next station<br>                j++; <br>            }<br><br>            // If all stops are covered and fuel is non-negative, return the starting station<br>            if (stopCount == n &amp;&amp; totalFuel &gt;= 0) {<br>                return i;<br>            }<br>        }<br><br>        // If no valid starting point is found, return -1<br>        return -1;<br>    }<br><br>    public static void main(String[] args) {<br>        // Declare example inputs for gas and cost arrays<br>        int[] gas = {1, 2, 3, 4, 5};<br>        int[] cost = {3, 4, 5, 1, 2};<br><br>        // Find the starting gas station<br>        int result = canCompleteCircuit(gas, cost);<br><br>        // Display the result<br>        if (result != -1) {<br>            // Display the starting station if the journey is possible<br>            System.out.println(&quot;The circuit can be completed starting from gas station: &quot; + result);<br>        } else {<br>            // Display a message if the journey is not possible<br>            System.out.println(&quot;It is not possible to complete the circuit from any gas station.&quot;);<br>        }<br>    }<br>}</pre><blockquote><strong><em>Python Code 👩‍💻:</em></strong></blockquote><pre># Function to find the starting gas station<br>def can_complete_circuit(gas, cost):<br>    # Number of gas stations<br>    n = len(gas)  <br><br>    # Loop to test each station as a potential starting point<br>    for i in range(n):<br>        # Initialize total fuel to 0<br>        total_fuel = 0  <br><br>        # Track the number of stops made<br>        stop_count = 0  <br><br>        # Start journey from the current station<br>        j = i  <br><br>        # Simulate the journey<br>        while stop_count &lt; n:<br>            # Calculate the remaining fuel after reaching the next station<br>            total_fuel += gas[j % n] - cost[j % n]<br><br>            # If total fuel becomes negative, the journey fails<br>            if total_fuel &lt; 0:<br>                break<br><br>            # Increment the stop count<br>            stop_count += 1  <br><br>            # Move to the next station<br>            j += 1  <br><br>        # If all stops are covered and fuel is non-negative, return the starting station<br>        if stop_count == n and total_fuel &gt;= 0:<br>            return i<br><br>    # If no valid starting point is found, return -1<br>    return -1<br><br><br>if __name__ == &quot;__main__&quot;:<br>    # Declare example inputs for gas and cost arrays<br>    gas = [1, 2, 3, 4, 5]<br>    cost = [3, 4, 5, 1, 2]<br><br>    # Find the starting gas station<br>    result = can_complete_circuit(gas, cost)<br><br>    # Display the result<br>    if result != -1:<br>        # Display the starting station if the journey is possible<br>        print(f&quot;The circuit can be completed starting from gas station: {result}&quot;)<br>    else:<br>        # Display a message if the journey is not possible<br>        print(&quot;It is not possible to complete the circuit from any gas station.&quot;)</pre><blockquote><strong><em>Javascript Code 👩‍💻:</em></strong></blockquote><pre>// Function to find the starting gas station<br>function canCompleteCircuit(gas, cost) {<br>    const n = gas.length; // Number of gas stations<br><br>    // Loop to test each station as a potential starting point<br>    for (let i = 0; i &lt; n; i++) {<br>        // Initialize total fuel to 0<br>        let totalFuel = 0; <br><br>        // Track the number of stops made<br>        let stopCount = 0; <br><br>        // Start journey from the current station<br>        let j = i; <br><br>        // Simulate the journey<br>        while (stopCount &lt; n) {<br>            // Calculate the remaining fuel after reaching the next station<br>            totalFuel += gas[j % n] - cost[j % n];<br><br>            // If total fuel becomes negative, the journey fails<br>            if (totalFuel &lt; 0){<br>                break;<br>            }<br><br>            // Increment the stop count<br>            stopCount++; <br><br>            // Move to the next station<br>            j++; <br>        }<br><br>        // If all stops are covered and fuel is non-negative, return the starting station<br>        if (stopCount === n &amp;&amp; totalFuel &gt;= 0) {<br>            return i;<br>        }<br>    }<br><br>    // If no valid starting point is found, return -1<br>    return -1;<br>}<br><br>// Example inputs for gas and cost arrays<br>const gas = [1, 2, 3, 4, 5];<br>const cost = [3, 4, 5, 1, 2];<br><br>// Find the starting gas station<br>const result = canCompleteCircuit(gas, cost);<br><br>// Display the result<br>if (result !== -1) {<br>    // Display the starting station if the journey is possible<br>    console.log(`The circuit can be completed starting from gas station: ${result}`);<br>} else {<br>    // Display a message if the journey is not possible<br>    console.log(&quot;It is not possible to complete the circuit from any gas station.&quot;);<br>}</pre><p><em>🌐🌐 </em><strong><em>Complexity Analysis:</em></strong></p><blockquote><em>⏰⏰ </em><strong><em>Time Complexity</em></strong><em>:</em> <em>The brute-force approach tests every station as a potential starting point and simulates the entire journey for each station. This involves:<br>1. </em><strong><em>Outer loop:</em></strong><em> Iterating through all </em><em>n stations to select a starting point.<br>2. </em><strong><em>Inner loop:</em></strong><em> For each starting point, traversing all </em><em>n stations in a circular manner.<br>This gives us an approximate time complexity of </em><strong><em>O(n²)</em></strong><em>, where </em><em>n is the number of stations. However, in some variations, with additional checks, the complexity might appear closer to </em><strong><em>O(n³)</em></strong><em> due to redundant calculations, but it is generally simplified to </em><strong><em>O(n²)</em></strong><em> for this brute-force simulation.</em></blockquote><blockquote><em>🚀🚀 </em><strong><em>Space Complexity</em></strong><em>: The algorithm does not use any additional data structures. All calculations are performed in place, and variables like </em><em>totalFuel and </em><em>stopCount are scalar variables.</em></blockquote><blockquote><em>Thus, the </em><strong><em>space complexity is O(1)</em></strong><em> as no extra memory is used.</em></blockquote><p><strong><em>Catch 🫨:</em></strong><em> </em>The brute force approach for this problem is highly inefficient as it tests every station as a starting point and simulates a full journey for each. This results in a time complexity of <strong>O(n²)</strong>, which becomes impractical for large input sizes. To optimize further, instead of restarting from every station, we can eliminate invalid stations as we traverse. This way, we reduce unnecessary computations and ensure a more efficient solution.</p><p><strong><em>📝NOTE :</em></strong><em> </em>Our brute-force approach simulates starting the journey from each station and stops as soon as the gas becomes negative, indicating that the current station cannot be a valid starting point. Then, it moves to the next station and repeats the process. For example, starting at station 0 but failing to reach station 1 due to insufficient gas, the algorithm moves to station 1 as the next potential starting point.</p><blockquote><strong><em>🎯 Optimal Approach :</em></strong></blockquote><p><em>💡💡 </em><strong><em>Intuition : </em></strong>If the car fails to complete a trip from a starting point, it means that up to that failure point, the fuel accumulation was either surplus or just breaking even. If there was a deficit earlier, the car would have already run out of gas before reaching the failure point. Hence, the failure at station i indicates a deficit at that point.<br>This insight allows us to skip testing all stations between the current starting point and the failure point. Instead, we can jump directly to the next station after the failure point.</p><p><strong><em>🚀 🚀 Approach:</em></strong></p><ol><li>Track totalSurplus (total gas - cost across all stations).</li><li>Track surplus (current gas balance during the trip).</li><li>Traverse through all stations:</li></ol><ul><li>Update surplus and totalSurplus:</li></ul><pre>surplus += gas[i] - cost[i]<br>totalSurplus += gas[i] - cost[i]</pre><ul><li>If surplus &lt; 0:</li><li>Reset surplus to 0.</li><li>Update start to i + 1 (next station)</li></ul><p>4. If totalSurplus &lt; 0, return -1. Otherwise, return start.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/1*TQKGYuKaTRixZQ8FjNWWBw.png" /></figure><p>If the car fails to complete a trip from a starting point, it means that up to that failure point, the fuel accumulation was either surplus or just breaking even. If there was a deficit earlier, the car would have already run out of gas before reaching the failure point. Hence, the failure at station i indicates a deficit at that point.</p><p>As a result, all stations between the starting point and station i are also invalid starting points since they would lead to the same deficit. Therefore, the algorithm can skip these stations and begin testing from station i+1.</p><p><em>🤖🤖 </em><strong><em>Codes :</em></strong></p><blockquote><strong><em>C++ Code 👩‍💻:</em></strong></blockquote><pre>#include &lt;iostream&gt;<br>#include &lt;vector&gt;<br>using namespace std;<br><br>// Function to find the starting gas station<br>int canCompleteCircuit(vector&lt;int&gt;&amp; gas, vector&lt;int&gt;&amp; cost) {<br>    // Get the number of gas stations<br>    int n = gas.size(); <br><br>    // Tracks total fuel surplus across all stations<br>    int total_surplus = 0; <br><br>    // Tracks current fuel surplus for the current journey<br>    int surplus = 0; <br><br>    // Potential starting station<br>    int start = 0; <br><br>    // Iterate through all gas stations<br>    for (int i = 0; i &lt; n; i++) {<br>        // Update total surplus and current surplus<br>        total_surplus += gas[i] - cost[i];<br>        surplus += gas[i] - cost[i];<br><br>        // If the current surplus is negative, the current journey fails<br>        if (surplus &lt; 0) {<br>            // Reset surplus for a new potential journey<br>            surplus = 0; <br><br>            // Move the starting station to the next station<br>            start = i + 1; <br>        }<br>    }<br><br>    // If the total surplus is negative, return -1 (no valid journey possible)<br>    if(total_surplus &lt; 0){<br>       return -1;<br>    }<br><br>    // Otherwise, return the starting station<br>    return start;<br>}<br><br>int main() {<br>    // Example inputs for gas and cost arrays<br>    vector&lt;int&gt; gas = {1, 2, 3, 4, 5};<br>    vector&lt;int&gt; cost = {3, 4, 5, 1, 2};<br><br>    // Find the starting gas station<br>    int result = canCompleteCircuit(gas, cost);<br><br>    // Display the result<br>    if (result != -1) {<br>        cout &lt;&lt; &quot;The circuit can be completed starting from gas station: &quot; &lt;&lt; result &lt;&lt; endl;<br>    } else {<br>        cout &lt;&lt; &quot;It is not possible to complete the circuit from any gas station.&quot; &lt;&lt; endl;<br>    }<br><br>    return 0;<br>}</pre><blockquote><strong><em>Java Code 👩‍💻:</em></strong></blockquote><pre>import java.util.*;<br><br>public class GasStation {<br>    // Function to find the starting gas station<br>    public static int canCompleteCircuit(int[] gas, int[] cost) {<br>        // Number of gas stations<br>        int n = gas.length; <br>    <br>        // Tracks total fuel surplus across all stations<br>        int totalSurplus = 0; <br><br>        // Tracks current fuel surplus for the current journey<br>        int surplus = 0; <br><br>        // Potential starting station<br>        int start = 0; <br><br>        // Iterate through all gas stations<br>        for (int i = 0; i &lt; n; i++) {<br>            // Update total surplus and current surplus<br>            totalSurplus += gas[i] - cost[i];<br>            surplus += gas[i] - cost[i];<br><br>            // If the current surplus is negative, the current journey fails<br>            if (surplus &lt; 0) {<br>                // Reset surplus for a new potential journey<br>                surplus = 0; <br> <br>                // Move the starting station to the next station<br>                start = i + 1; <br>            }<br>        }<br><br>        // If the total surplus is negative, return -1 (no valid journey possible)<br>        if(totalSurplus &lt; 0){<br>           return -1;<br>        }<br><br>        // Otherwise, return the starting station<br>        return start;<br>    }<br><br>    public static void main(String[] args) {<br>        // Example inputs for gas and cost arrays<br>        int[] gas = {1, 2, 3, 4, 5};<br>        int[] cost = {3, 4, 5, 1, 2};<br><br>        // Find the starting gas station<br>        int result = canCompleteCircuit(gas, cost);<br><br>        // Display the result<br>        if (result != -1) {<br>            System.out.println(&quot;The circuit can be completed starting from gas station: &quot; + result);<br>        } else {<br>            System.out.println(&quot;It is not possible to complete the circuit from any gas station.&quot;);<br>        }<br>    }<br>}</pre><blockquote><strong><em>Python Code 👩‍💻:</em></strong></blockquote><pre># Function to find the starting gas station<br>def can_complete_circuit(gas, cost):<br>    # Number of gas stations<br>    n = len(gas)  <br><br>    # Tracks total fuel surplus across all stations<br>    total_surplus = 0  <br><br>    # Tracks current fuel surplus for the current journey<br>    surplus = 0 <br><br>    # Potential starting station<br>    start = 0  <br><br>    # Iterate through all gas stations<br>    for i in range(n):<br>        # Update total surplus and current surplus<br>        total_surplus += gas[i] - cost[i]<br>        surplus += gas[i] - cost[i]<br><br>        # If the current surplus is negative, the current journey fails<br>        if surplus &lt; 0:<br>            # Reset surplus for a new potential journey<br>            surplus = 0  <br><br>            # Move the starting station to the next station<br>            start = i + 1  <br><br>    # If the total surplus is negative, return -1 (no valid journey possible)<br>    if total_surplus &lt; 0:<br>       return -1<br><br><br>    # Otherwise, return the starting station<br>    return start<br><br><br>if __name__ == &quot;__main__&quot;:<br>    # Example inputs for gas and cost arrays<br>    gas = [1, 2, 3, 4, 5]<br>    cost = [3, 4, 5, 1, 2]<br><br>    # Find the starting gas station<br>    result = can_complete_circuit(gas, cost)<br><br>    # Display the result<br>    if result != -1:<br>        print(f&quot;The circuit can be completed starting from gas station: {result}&quot;)<br>    else:<br>        print(&quot;It is not possible to complete the circuit from any gas station.&quot;)</pre><blockquote><strong><em>Javascript Code 👩‍💻:</em></strong></blockquote><pre>// Function to find the starting gas station<br>function canCompleteCircuit(gas, cost) {<br>    // Number of gas stations<br>    const n = gas.length; <br><br>    // Tracks total fuel surplus across all stations<br>    let totalSurplus = 0; <br><br>    // Tracks current fuel surplus for the current journey<br>    let surplus = 0; <br><br>    // Potential starting station<br>    let start = 0; <br><br>    // Iterate through all gas stations<br>    for (let i = 0; i &lt; n; i++) {<br>        // Update total surplus and current surplus<br>        totalSurplus += gas[i] - cost[i];<br>        surplus += gas[i] - cost[i];<br><br>        // If the current surplus is negative, the current journey fails<br>        if (surplus &lt; 0) {<br>            // Reset surplus for a new potential journey<br>            surplus = 0; <br><br>            // Move the starting station to the next station<br>            start = i + 1; <br>        }<br>    }<br><br>    // If the total surplus is negative, return -1 (no valid journey possible)<br>    if(totalSurplus &lt; 0){<br>       return -1;<br>    }<br><br>    // Otherwise, return the starting station<br>    return start;<br>}<br><br>// Example inputs for gas and cost arrays<br>const gas = [1, 2, 3, 4, 5];<br>const cost = [3, 4, 5, 1, 2];<br><br>// Find the starting gas station<br>const result = canCompleteCircuit(gas, cost);<br><br>// Display the result<br>if (result !== -1) {<br>    console.log(`The circuit can be completed starting from gas station: ${result}`);<br>} else {<br>    console.log(&quot;It is not possible to complete the circuit from any gas station.&quot;);<br>}</pre><blockquote><em>⏰⏰ </em><strong><em>Time Complexity</em></strong><em>: The optimal approach processes the entire array of stations in a single pass, calculating the total surplus and tracking the current surplus as it iterates. This involves:<br>1. A </em><strong><em>single loop</em></strong><em> through the </em><em>n stations to calculate the total surplus and determine the starting station.<br>This gives a </em><strong><em>time complexity of O(n)</em></strong><em>, where </em><em>n is the number of stations. Since it only requires one traversal of the arrays, the algorithm is highly efficient.</em></blockquote><blockquote><em>🚀🚀 </em><strong><em>Space Complexity:</em></strong><em> The algorithm does not use any additional data structures. All calculations are performed in place, and variables like </em><em>totalFuel and </em><em>stopCount are scalar variables.</em></blockquote><blockquote><em>Thus, the </em><strong><em>space complexity is O(1)</em></strong><em> as no extra memory is used.</em></blockquote><blockquote>💁‍♂️💁‍♂️ <strong><em>Learning Tips:</em></strong></blockquote><p>Focus on deriving insights from the problem’s structure.</p><ul><li>Always start with a brute-force approach to build understanding.</li><li>Use patterns in failures to optimize redundant work.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dba63c23b6f9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Count number of subarrays whose sum equals to k]]></title>
            <link>https://suren015.medium.com/count-number-of-subarrays-whose-sum-equals-to-k-aeca142a43f3?source=rss-9aa46c28d293------2</link>
            <guid isPermaLink="false">https://medium.com/p/aeca142a43f3</guid>
            <dc:creator><![CDATA[Surendra Tholiya]]></dc:creator>
            <pubDate>Fri, 27 Sep 2024 10:29:44 GMT</pubDate>
            <atom:updated>2024-09-27T10:29:44.739Z</atom:updated>
            <content:encoded><![CDATA[<p><strong><em>✍️ Problem Statement:</em></strong></p><p>Given an array of integers nums and an integer k, return <em>the total number of subarrays whose sum equals to</em> k. A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p><p><strong>Example 1:</strong></p><pre>Input: nums = [1,1,1], k = 2<br>Output: 2</pre><p><strong>Example 2:</strong></p><pre>Input: nums = [1,2,3], k = 3<br>Output: 2</pre><p><strong>Constraints:</strong></p><ul><li>1 ≤ nums.length ≤ 2 * 1⁰⁴</li><li>-1000 ≤ nums[i] ≤ 1000</li><li>-1⁰⁷ ≤ k ≤ 1⁰⁷</li></ul><p><strong><em>Note:</em></strong></p><p>For an array of size n:</p><ol><li>A subarray can start at any of its n positions.</li><li>And for each starting position, the length of the subarray can range between 1 to n depending on the number of remaining elements.</li></ol><p>So the maximum possible number of subarrays for any array of size n will be = N (Let’s say) = n + (n-1) + (n-2) + …..+ 1 = (n * (n+1))/2. For an array of integers each of its subarrays will have a sum (sum of all the elements of that subarray), now we have to find out the total number of subarrays whose sum will be equal to k (will be given) out of the N possible subarrays.</p><p>Let’s walk towards the solution!!<strong>🚶‍♂️‍➡️🚶‍♂️‍➡️</strong>‍</p><h3>Solution: 🔥🔥</h3><p>Let us consider the size of the given array to be n.</p><blockquote><strong><em>🎯 Brute Force Approach:</em></strong></blockquote><p>The first thing that comes into our mind when we think of a solution for this problem would be “ finding the sum of all possible subarrays of the given array and count the ones whose sum is equal to k (given) ”, as simple as that.</p><p><strong><em>Intuition:</em></strong></p><ol><li>List all the subarrays of the given array.</li><li>Find out the sum of each suabarray.</li><li>Count the total number of subarrays whose sum is equal to k.</li></ol><p><strong><em>Algorithm :</em></strong></p><p>1: Run a loop that will <strong>select every possible starting index</strong> (say start) of the subarray.</p><p>2: Inside this loop, run another loop that will <strong>signify the ending index</strong> (say end) of the subarray.</p><p>3: After that for each subarray starting from the index start and ending at the index end i.e, for nums[start…end]<strong>, </strong>run another loop to <strong>calculate the sum of all the elements of that particular subarray</strong>.</p><p>4: For each subarray after calculating the sum, <strong>check if the sum is equal to k</strong> (given). If it is, increment the value of the count by 1.</p><p>👩‍💻👨‍💻 Code the above algorithm in which ever programming language you are comfortable in. Below is the C++ implementation for the same.</p><p><strong>C++ Code 👩‍💻:</strong></p><pre>#include &lt;bits/stdc++.h&gt;<br>using namespace std;<br><br>int CountSubarraysWithGivenSum(vector&lt;int&gt;&amp; nums, int k) {<br>    int n = nums.size();                           // size of the given array.<br>    int count = 0;                                // Number of subarrays:<br>    for (int start = 0 ; start &lt; n; start++) {    // starting index - start<br>        for (int end = start; end &lt; n; end++) {   // ending index - end<br>            // calculate the sum of the subarray[start...end]<br>            int subarray_sum = 0;<br>            for (int current = start; current &lt;= end; current++) {<br>                subarray_sum += nums[current];<br>            }<br>            // Increment the count if the current subarray sum is equal to k<br>            if (subarray_sum == k) {<br>                count++;<br>            } <br>        }<br>    }<br>    return count;<br>}<br>int main()<br>{<br>    vector&lt;int&gt; nums= {1, 2, 3, 4};<br>    int k = 5;<br>    int count = CountSubarraysWithGivenSum(nums, k);<br>    cout &lt;&lt; &quot;Total number of subarrays whose sum is k: &quot; &lt;&lt; count;<br>    return 0;<br>}</pre><p><strong>Complexity Analysis:</strong></p><blockquote><em>Time Complexity: </em><strong><em>O(n³)</em></strong><em> — Three nested loops are being used in the above algorithm. Though all are not running for exactly n times, the time complexity will be approximately O(n³), where n = size of the array.</em></blockquote><blockquote><em>Space Complexity: </em><strong><em>O(1)</em></strong><em> — As we are not using any extra space.</em></blockquote><p><strong><em>Catch</em></strong><em> </em>🫨: This could be highly inefficient when the size of the array is large, to optimize this further we can discard the inner loop which was used to calculate the subarray sum, instead we can just add the current element to the previous subarray to get the current subarray sum. So let’s try to implement the idea.</p><blockquote><em>🎯 </em><strong><em>Better Approach:</em></strong></blockquote><p>If we carefully observe, we can notice that to get the sum of the current subarray we just need to add the current element(i.e. <strong>arr[end]</strong>) to the sum of the previous subarray i.e. <strong>arr[start….end-1]</strong>.</p><p><strong><em>Algorithm:</em></strong></p><p>1:, 2: would remain the same</p><p>3: Inside the ending index loop , add the current element to the sum of the previous subarray i.e. <strong>subarrray_sum = subarray_sum + arr[end]</strong>.</p><p>4: After calculating the sum, <strong>check if the sum is equal to the given k</strong>. If it is, increment the value of the count by 1.</p><p>Below is the C++ implementation for the same.</p><p><strong>C++ Code</strong> 👩‍💻:</p><pre>#include &lt;bits/stdc++.h&gt;<br>using namespace std;<br><br>int CountSubarraysWithGivenSum(vector&lt;int&gt;&amp; nums, int k) {<br>    int n = nums.size();                   // size of the given array.<br>    int count = 0;                          // Number of subarrays:<br>    for (int start = 0 ; start &lt; n; start++) {        // starting index i<br>        int subarray_sum = 0;<br>        for (int end = start; end &lt; n; end++) {     // ending index j<br>            // calculate the sum of the subarray [start...end]<br>            // sum of [start..end-1] + arr[end]<br>            subarray_sum += nums[end];<br>            // Increment the count if the subarray sum is equal to k:<br>            if (subarray_sum == k)<br>                count++;<br>        }<br>    }<br>    return count;<br>}<br>int main()<br>{<br>    vector nums= {1, 2, 3, 4};<br>    int k = 5;<br>    int count = CountSubarraysWithGivenSum(nums, k);<br>    cout &lt;&lt; &quot;Total number of subarrays whose sum is k: &quot; &lt;&lt; count;<br>    return 0;<br>}</pre><p><strong>Complexity Analysis:</strong></p><blockquote><em>Time Complexity: </em><strong><em>O(n²)</em></strong><em> — Two nested loops are being used in the above algorithm. Each of them will run for exactly n times, the time complexity will be O(n²), where n = size of the array.</em></blockquote><blockquote><em>Space Complexity: </em><strong><em>O(1)</em></strong><em> — As we are not using any extra space.</em></blockquote><p><strong>Note: </strong>O(n²)<strong> </strong>can still be inefficient for large arrays. Can we do better?</p><p><strong>🤔💭🤯 Here’s the challenge:</strong> Can we avoid recalculating sums for overlapping subarrays?</p><blockquote><em>🎯 </em><strong><em>Optimal</em></strong><em> </em><strong><em>Approach:</em></strong></blockquote><p>The key observation here is that sums of subarrays overlap. What if we could remember the cumulative sum up to the current index and use that information to make future calculations easier?</p><p>✍️ Let’s introduce the idea of a <strong>prefix sum</strong>:</p><ul><li>The prefix sum up to an index i is the sum of all elements from the start of the array to the index i.</li><li><strong>Intuition: </strong>A key observation is that the sum of a subarray [i, j] is equal to the sum of [0, j] minus the sum of [0, i-1]. So if we know the prefix sum up to two different points in the array, we can quickly check if the sum between them is k.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*CLcAXlDZAdK6PVHc.png" /></figure><p>Here’s an interesting observation:</p><ul><li>Let’s say the prefix sum up to index i is x, and we know that some subarray starting earlier has a prefix sum of x−k.</li><li>Then, the subarray between these two points must have a sum of k!</li></ul><p>Can we store these prefix sums as we compute them? What if we used a hash map to store the frequency of prefix sums we’ve seen so far? This way, for each prefix sum x at index i, we can quickly check if x−k has appeared before.</p><p><strong><em>Algorithm:</em></strong></p><p>1:<strong> Declare a map</strong> to store the prefix sums and their counts.</p><p>2:<strong> Initialize</strong> the map by setting the value of <strong>0</strong> as <strong>1</strong> to account for the case where a prefix sum equals k from the start of the array.</p><p>3: <strong>Run a loop</strong> (let’s call it i) that will iterate from index <strong>0</strong> to <strong>n-1</strong> (where <strong>n</strong> is the size of the array).</p><p>4: For each index <strong>i</strong>:</p><ul><li><strong>Maintain a variable</strong> (let’s call it currentPrefixSum) to store the cumulative prefix sum as we iterate through the array.</li><li><strong>Add the current element</strong> nums[i] to currentPrefixSum.</li></ul><p>5:<strong> Calculate</strong> the value of currentPrefixSum-k (let’s call it targetSum). This value represents the prefix sum we need to find in the map to determine how many subarrays ending at index <strong>i</strong> sum to <strong>k</strong>.</p><p>6:<strong> Check the map</strong> for the occurrence of targetSum.</p><p>7: If it exists, <strong>add</strong> the occurrence count of targetSum from the map to our total count of subarrays whose sum equals k.</p><p>8:<strong> Store</strong> the current prefix sum in the map, incrementing its occurrence by <strong>1</strong>. This way, we account for the current prefix sum for future indices.</p><p>So excited to code this !! 🫣👩‍💻</p><p><strong>C++ Code</strong> 👩‍💻:</p><pre>#include &lt;bits/stdc++.h&gt;<br>using namespace std;<br><br>int CountSubarraysWithGivenSum(vector&lt;int&gt;&amp; nums, int k) {<br>    int n = nums.size();                         // size of the given array.<br>    map&lt;int, int&gt; mp;                 <br>    int count = 0;                               // Number of subarrays:<br>    int currentPrefixSum = 0;                    // Current prefix sum<br>    mp[0] = 1;                                   // Initialize the map with 0 as a prefix sum<br>    for (int i = 0; i &lt; n; i++) {<br>        // Add the current element to the prefix sum<br>        currentPrefixSum += nums[i];<br>        // Calculate the target prefix sum that needs to be found in the map<br>        int targetSum = currentPrefixSum - k;<br>        // Add the number of times targetSum has occurred before to count<br>        count += mp[targetSum];<br>        // Update the count of the current prefix sum in the map<br>        mp[currentPrefixSum]++;<br>    }                                 <br>    return count;<br>}<br>int main()<br>{<br>    vector nums= {1, 2, 3, 4};<br>    int k = 5;<br>    int count = CountSubarraysWithGivenSum(nums, k);<br>    cout &lt;&lt; &quot;Total number of subarrays whose sum is k: &quot; &lt;&lt; count;<br>    return 0;<br>}                        </pre><p><strong>Complexity Analysis:</strong></p><blockquote><em>Time Complexity: </em><strong><em>O(n) or O(n*log(n)) — </em></strong><em>depending on which map data structure we are using, where n = size of the array. If we are using an unordered_map in C++ the time complexity will be O(n) but if we are using a map, the time complexity will be O(n*log(n)).</em></blockquote><blockquote><em>Space Complexity: </em><strong><em>O(n)</em></strong><em> — as we are using a map data structure.</em></blockquote><p>In this article, we explored the problem of finding the number of contiguous subarrays that sum up to a given target k. Understanding this problem is crucial for mastering array manipulation and prefix sum techniques. I encourage you to practice this technique further to improve your understanding.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=aeca142a43f3" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>