Problem Statement

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's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Problem Explanation

Breaking the above problem statement we know that we need to find the starting gas station on a circular route where you can complete a full journey with the gas provided, when we deduct the travel costs.

Then we are asked to return the station’s index if travelling to the same gas station is possible; otherwise, return we return -1 if no solution exists.

In case you are wondering what’s a circular array?

Here a circular route implies that we have a circular array. That means when you reach the end of the array(n-1 index) you start back from start(0 index). Just like a circle with no actual start or end.

In a way you can say that the last element and the first element are neighbors.

Ideas:

1) The path is circular, i.e., a complete a full circle.

2) If the gasoline in all gas stations is less than the total fuel consumption of the route, it is impossible to complete the journey.

3) On the contrary, if the gasoline in all gas stations is greater than or equal to the total fuel consumption of the route, then there must be at least one station where you can start and complete the journey.

Examples

Let’s consider the following arrays for the dry run:

gas = [3, 0, 8, 2, 0, 0, 1]

cost = [2, 3, 4, 1, 2, 1, 3]

We need to find the starting gas station index, where if we start at that index, we can complete the circuit once.

Explanation:

Start at station 2:

At each station, we can see the following:

Station 2: We start with 8 units of gas.

Station 3: After traveling, the remaining gas is 4 + 2 (refill) — 1 (travel) = 5.

Station 4: After traveling, the remaining gas is 5 + 0 (refill) — 2 (travel) = 3.

Station 5: After traveling, the remaining gas is 3 + 0 (refill) — 1 (travel) = 2.

Station 6: After traveling, the remaining gas is 2 + 1 (refill) — 3 (travel) = 0.

Station 0: After traveling, the remaining gas is 0 + 3 (refill) — 2 (travel) = 1.

Station 1: After traveling, the remaining gas is 1 + 0 (refill) — 3 (travel) = -2, which prevents completing the loop.

We successfully made it back to station 0, so station 2 is a valid starting point.

Output : 2

Constraints

The given constraints are:

• n == gas.length == cost.length
• 1 <= n <=10^5
• 0 <= gas[i], cost[i] <= 10^4

Observations:

The values of gas filled in your car and costs of travelling are all positive and lies in range between 0 and 10000. Makes sense, we can’t have -ve petrol being added in your car after all.

The key observation is in fact the size of array which lies between 0 and 100000. This implies the solution must handle up to 100,000 gas stations efficiently.

A naive O(n²) approach will likely result in Time Limit Exceeded (TLE). A much better solution that can be acceptable might be O(nlogn) or O(n).

But O(nlogn) -> mostly refers to applying sorting techniques. Which in this case we know is not justifiable since we can’t change the order of gas stations.

So, the most feasible algorithm time complexity we can think of is O(n). Which generally happens in scenarios of linear search, two pointers, hashing, greedy or array manipulation techniques.

Hence the idea time complexity for the solution for the problem we will be looking at will be O(n).

BRUTE FORCE

The first step to solving every coding problem is coming up with a brute force or the most simplest method to solve the problem.

Intuition

The most basic form of brute force is simulating the process in the problem.

Our idea is to try starting at every gas station and simulate the journey to check if completing the circuit is possible.

According to the problem, the formula for calculating the amount of remaining gasoline at each station is: currGas - cost[i] + gas[i+1].

where,

currGas -> is the current gas available in the car

i -> represents the current gas station our car is on.

It should be noted that if gas[i+1]the range exceeds the gas length, it needs to start from 0.

For every gas station we start our journey and check if we can reach back while fulfilling the condition that the gas inside the car never becomes less than 0 while travelling.

The car will only move forward when: currGas — cost[i] >= 0

Otherwise, the car can’t reach the next gas station since gas will be over before.

Approach

Step I: Start at every gas station index i.

Step II: Simulate the journey track the remaining gas as you travel.

Step III: Move to the next station, adjusting the remaining gas (currGas += gas[i] - cost[i]).

Step IV: Use modulo (%) to handle the circular nature of the problem.

i.e., if(i>n) i = (i % n)

Step V: If at any point the gas becomes negative(i.e., currGas<0), the journey fails for the current starting index.

Step VI: If you can complete the circle, return the starting index. If no starting index works, return -1.

Dry Run

Example:

Input:

gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

Execution:

● Start at station 0:

• Remaining gas after station 0: 1 - 3 = -2 (Fails)

● Start at station 1:

• Remaining gas after station 1: 2 - 4 = -2 (Fails)

● Start at station 2:

• Remaining gas after station 2: 3 - 5 = -2 (Fails)

● Start at station 3:

• Remaining gas after station 3: 4 - 1 = 3
• Remaining gas after station 4: 3 + 5 - 2 = 6
• Remaining gas after station 0: 6 + 1 - 3 = 4
• Remaining gas after station 1: 4 + 2 - 4 = 2
• Remaining gas after station 2: 2 + 3 - 5 = 0 (Completes)
• Success: Return 3.

Output : 3

Code : C++

// Approach: Find the starting gas station for a circular route
// Language: C++

#include <iostream>
#include <vector>
using namespace std;

// Class to solve the gas station circuit problem
class GasStationCircuit {

public:
    // Function to find the starting gas station
    int CanCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();  // Number of stations

        // Try starting from each gas station
        for (int start = 0; start < n; start++) {
            int remaining_gas = 0;  
            bool completed = true;  

            // Simulate the journey
            for (int i = 0; i < n; i++) {
                int current_station = (start + i) % n;

                remaining_gas += gas[current_station] - cost[current_station];

                // If remaining gas is negative, this start fails
                if (remaining_gas < 0) {
                    completed = false;
                    break;
                }
            }

            // If the circuit is completed, return the start station
            if (completed) {
                return start;
            }
        }

        // If no valid starting station is found, return -1
        return -1;
    }
};

// Main function
int main() {
    // Create an instance of the class
    GasStationCircuit circuit;

    // Gas and cost arrays for the circuit
    vector<int> gas = {1, 2, 3, 4, 5};
    vector<int> cost = {3, 4, 5, 1, 2};

    // Find and display the starting station
    int result = circuit.CanCompleteCircuit(gas, cost);
    cout << "Starting station: " << result << endl;

    return 0;
}

Code : Java

// Approach: Find the starting gas station for a circular route
// Language: Java

public class GasStationCircuit {

    // Method to find the starting gas station
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // Initialize the number of stations
        int n = gas.length;

        // Try starting from each gas station
        for (int start = 0; start < n; start++) {
            // Track the remaining gas during the journey
            int remainingGas = 0;

            // Flag to check if the journey is completed
            boolean completed = true;

            // Simulate the journey
            for (int i = 0; i < n; i++) {
                int currentStation = (start + i) % n;

                // Update remaining gas after traveling
                remainingGas += gas[currentStation] - cost[currentStation];

                // If remaining gas is negative, this start fails
                if (remainingGas < 0) {
                    completed = false;
                    break;
                }
            }

            // If the circuit is completed, return the start station
            if (completed) {
                return start;
            }
        }

        // If no valid starting station is found, return -1
        return -1;
    }

    public static void main(String[] args) {
        // Create an instance of the class
        GasStationCircuit circuit = new GasStationCircuit();

        // Gas and cost arrays for the circuit
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};

        // Find and display the starting station
        int result = circuit.canCompleteCircuit(gas, cost);
        System.out.println("Starting station: " + result);
    }
}

Code : Python

# Approach: Find the starting gas station for a circular route
# Language: Python

class GasStationCircuit:
    
    # Function to find the starting gas station
    def can_complete_circuit(self, gas, cost):
        n = len(gas)  # Number of stations

        # Try starting from each gas station
        for start in range(n):
            remaining_gas = 0  
            completed = True  

            # Simulate the journey
            for i in range(n):
                current_station = (start + i) % n

                remaining_gas += gas[current_station] - cost[current_station]

                # If remaining gas is negative, this start fails
                if remaining_gas < 0:
                    completed = False
                    break

            # If the circuit is completed, return the start station
            if completed:
                return start

        # If no valid starting station is found, return -1
        return -1


# Main function
if __name__ == "__main__":
    # Create an instance of the class
    circuit = GasStationCircuit()

    # Gas and cost arrays for the circuit
    gas = [1, 2, 3, 4, 5]
    cost = [3, 4, 5, 1, 2]

    # Find and display the starting station
    result = circuit.can_complete_circuit(gas, cost)
    print("Starting station:", result)

Code : JavaScript

// Approach: Find the starting gas station for a circular route
// Language: JavaScript

// Class name in PascalCase
class GasStationCircuit {
    
    // Function to find the starting gas station
    canCompleteCircuit(gas, cost) {
        let n = gas.length; 

        // Try starting from each gas station
        for (let start = 0; start < n; start++) {
            let remainingGas = 0;  
            let completed = true;  

            // Simulate the journey
            for (let i = 0; i < n; i++) {
                let currentStation = (start + i) % n;

                remainingGas += gas[currentStation] - cost[currentStation];

                // If remaining gas is negative, this start fails
                if (remainingGas < 0) {
                    completed = false;
                    break;
                }
            }

            // If the circuit is completed, return the start station
            if (completed) {
                return start;
            }
        }

        // If no valid starting station is found, return -1
        return -1;
    }
}

// Main function
const circuit = new GasStationCircuit();

// Gas and cost arrays for the circuit
const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];

// Find and display the starting station
const result = circuit.canCompleteCircuit(gas, cost);
console.log("Starting station:", result);

Time Complexity: O(n²)

The outer loop iterates over each station (n times). For each station, we traverse through the entire circuit (n stations).

This gives us two nested loops, resulting in a time complexity of O(n) * O(n) = O(n²).

Space Complexity: O(1)

The algorithm uses a constant amount of space. It only requires variables to store the remainingGas and completed status, and no additional data structures are used. Thus, the space complexity is constant.

Short Bridge between Brute Force and Optimal Solution

On running the above brute force solution you will find that the above code returns a TLE solution. We expected a Time Limit Exceed scenario in our above discussion, given the reason the constraint son the size of array is too high for the code to run in a limited amount of time and is in fact very slow.

Brute force methods are usually slow because they check all possibilities without skipping any, leading to a lot of repeated calculations.

The first step to making our code faster is to:

1. Avoid Repeated Work

Imagine we have two pointers, i and j, both starting at the same position. As j moves forward, we keep checking different positions it reaches:

* * * * * *
      ^
      i
      ^
      j

As j moves ahead:

* * * * * *
      ^ ^
      i j

Eventually, j reaches the end and comes back to the beginning. If we've already checked a position before, we don't need to check it again.

For example, if we’ve already checked that from station 0 we can reach station 2. Then we can say that we can jump directly to station 2 next time, instead of going all the way back through station 0. This saves time by skipping repeated calculations.

* * * * * *
    ^ ^   
    j i

By keeping track of how far each position can go and how much “fuel” it has left, we can skip recalculating the same things and make the process much faster.

2. Skipping Loops

Since we found out that the positions between i and j can form a loop. This means that instead of checking each position one by one, we can skip over them because they would only bring us back to the same places.

For example, if we know that station i can reach station j and that station (i+1) can also reach j, it means we don’t need to start over from i+1. We can skip directly to the next position and avoid wasting time checking the same things over again.

Optimal Solution

Intuition

Now from the above discussion we understood that:

• If at any point during the journey, the fuel in the tank becomes negative, it means that starting from the previous station isn’t feasible.
• We need to balance the total gas and total cost across all stations. If the total gas is less than the total cost, the journey isn’t possible, and we should return -1.
• If the journey is possible, the solution will be unique because there is exactly one starting station that allows the circuit to be completed. [Already, given in the problem statement, not something you should worry about]

Why This is Greedy

This approach is greedy because at each station, you make the best choice by moving to the farthest station you can reach, using the available resources efficiently. You don’t reconsider previous decisions, and you don’t waste fuel going back. You’re always making the best local decision (choosing the farthest point) with the hope that it leads to the global optimal solution.

In simple terms: Greedy = Always moving forward with the farthest reachable option at each step.

Scenario:

Imagine you are at Station A, and you want to travel to Station C, with Station B in between. Each station has a certain amount of gas that allows you to reach the next station.

Let’s represent this as:

Station A --> Station B --> Station C

Now, you have a certain amount of fuel at Station A, and you want to reach Station C. The greedy approach works by always choosing the farthest station you can reach at each step, without revisiting any station.

1. At Station A, you start with a certain amount of fuel. You check how far you can go:You can reach Station B.
2. At Station B, you look at how far you can go from there: You can reach Station C.
3. Now, instead of going back and checking Station A again (which would waste time), you directly jump from Station B to Station C, using the remaining fuel.

Approach

Step I : Check the possibility:

• First, we check if the total amount of gas is enough to cover the total cost. If the total gas is less than the total cost, return -1 immediately because it is impossible to complete the circuit.

Step I : Simulate the Journey:

• Initialize two variables: total_sum and current_sum.

total_sum keeps track of the overall difference between total gas and total cost.

current_sum is used to simulate the journey from a particular start index.

• Traverse each gas station, calculating the difference gas[i] - cost[i]. Add this value to currGas.
• If currGas becomes negative at any station, it means the current starting index is not possible. Hence, we reset currGas and set the new potential starting station to the next station.
• After completing the loop, if totalGas is greater than or equal to 0, the last updated start index will be the valid starting point.

Edge Cases:

• If the total gas is less than total cost, return -1.
• If there is only one station, check if you can complete the circuit directly.

Dry Run

Let’s dry-run the example:

• Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]

Explanation:

Start by calculating the total sum of gas[i] - cost[i]:

• At index 0: gas[0] - cost[0] = 1 - 3 = -2
• At index 1: gas[1] - cost[1] = 2 - 4 = -2
• At index 2: gas[2] - cost[2] = 3 - 5 = -2
• At index 3: gas[3] - cost[3] = 4 - 1 = 3
• At index 4: gas[4] - cost[4] = 5 - 2 = 3

The total_sum is 0, which is non-negative, indicating a valid solution exists.

Now we start from index 3 because we see that the total sum at index 0,1,and 2 are negative. That means they are not feasible points at all.

• Starting at index 3:
• From index 3, fuel is 4 and the cost to move to index 4 is 1, so we have 4 - 1 = 3.
• Moving to index 4, fuel is 3 and the cost to move to index 0 is 2, so we have 3 - 2 = 1.
• Continuing the process we are able to complete the circuit

Output: 3

Code : C++

// Approach: Calculate the starting gas station for a circular trip
// Language: C++

#include <iostream>
#include <vector>
using namespace std;

// Function to calculate the starting gas station index
int CanCompleteCircuit(const vector<int>& gas, 
                       const vector<int>& cost) {

    // Initialize total sum and current sum
    int total_sum = 0;  
    int current_sum = 0;  
    int start_index = 0;

    // Loop through all the gas stations
    for (int i = 0; i < gas.size(); i++) {

        // Calculate the net gain of fuel at each station
        total_sum += gas[i] - cost[i];
        current_sum += gas[i] - cost[i];

        // If current sum becomes negative, reset the start index
        if (current_sum < 0) {
            current_sum = 0;
            start_index = i + 1;
        }
    }

    // If total sum is non-negative, return the start index, 
    // else return -1 indicating no valid circuit
    if (total_sum >= 0) {
        return start_index;
    } else {
        return -1;
    }
}

// Main function
int main() {
    // Example input for gas and cost
    vector<int> gas = {1, 2, 3, 4, 5};
    vector<int> cost = {3, 4, 5, 1, 2};

    // Call the function to find the starting index
    int result = CanCompleteCircuit(gas, cost);

    // Output the result
    cout << "Starting Index: " << result << endl;

    return 0;
}

Code : Java

// Approach: Find the starting gas station for a complete
// circuit if possible.
// Language: Java

public class GasStationCircuit {

    // Method to find the starting gas station for a circuit
    public int canCompleteCircuit(int[] gas, int[] cost) {
        
        // Initialize total sum and current sum
        int totalSum = 0;
        int currentSum = 0;
        
        // Initialize the starting index
        int startIndex = 0;

        // Iterate through the gas stations
        for (int i = 0; i < gas.length; i++) {

            // Calculate the difference between gas and cost
            totalSum += gas[i] - cost[i];
            currentSum += gas[i] - cost[i];

            // If current sum becomes negative, reset start index
            if (currentSum < 0) {
                currentSum = 0;
                startIndex = i + 1;
            }
        }

        // Return the start index if the total sum is non-negative
        // Else, return -1
        return totalSum >= 0 ? startIndex : -1;
    }
}

Code : Python

# Approach: Calculate the starting gas station for a circular trip
# Language: Python

def can_complete_circuit(gas, cost):
    
    # Initialize total sum and current sum
    total_sum = 0  
    current_sum = 0  
    start_index = 0

    # Loop through all the gas stations
    for i in range(len(gas)):
        
        # Calculate the net gain of fuel at each station
        total_sum += gas[i] - cost[i]
        current_sum += gas[i] - cost[i]

        # If current sum becomes negative, reset the start index
        if current_sum < 0:
            current_sum = 0
            start_index = i + 1

    # If total sum is non-negative, return the start index, 
    # else return -1 indicating no valid circuit
    if total_sum >= 0:
        return start_index
    else:
        return -1


# Main execution
if __name__ == "__main__":
    
    # Example input for gas and cost
    gas = [1, 2, 3, 4, 5]
    cost = [3, 4, 5, 1, 2]

    # Call the function to find the starting index
    result = can_complete_circuit(gas, cost)

    # Output the result
    print("Starting Index:", result)

Code : JavaScript

// Approach: Calculate the starting gas station for a circular trip
// Language: JavaScript

function canCompleteCircuit(gas, cost) {
    
    // Initialize total sum and current sum
    let totalSum = 0;
    let currentSum = 0;
    let startIndex = 0;

    // Loop through all the gas stations
    for (let i = 0; i < gas.length; i++) {
        
        // Calculate the net gain of fuel at each station
        totalSum += gas[i] - cost[i];
        currentSum += gas[i] - cost[i];

        // If current sum becomes negative, reset the start index
        if (currentSum < 0) {
            currentSum = 0;
            startIndex = i + 1;
        }
    }

    // If total sum is non-negative, return the start index, 
    // else return -1 indicating no valid circuit
    if (totalSum >= 0) {
        return startIndex;
    } else {
        return -1;
    }
}

// Main execution
const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];

// Call the function to find the starting index
const result = canCompleteCircuit(gas, cost);

// Output the result
console.log("Starting Index:", result);

Time Complexity: O(n)

Our code loops through the gas and cost arrays once, making it O(n), where n is the number of gas stations.

Space Complexity: O(1)

Our code uses only a few variables for tracking the sums and index, making it O(1).

DO THIS OR I WILL BE SAD 🥺

Solve a similar question to further deepen your understanding with the concepts we have discussed above. I am sure they will come handy in many questions. Here are some questions of similar nature and understanding:

2202. Maximize the Topmost Element After K Moves

455. Assign Cookies

135. Candy

Follow me on medium to get notification for all my amazing LeetCode editorials.

Find my other leetcode solution on my github — https://github.com/Harshit-Raj-14/My-Leetcode-Solutions . (Follow me and star mark the repo)

Best of Luck!

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

If you got to learn something valuable from this article and clap and follow me if you found it helpful.

Follow me for more such awesome articles that can help you in your interview preparation and studies and learn coding.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, tutorials, Coding Question solutions Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

“This Method Quickly Cured My Procrastination” — The Scientific Trick

Checkout the article now — Click here

Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Explanation : subarrays [1,1] and [1,1] have sum equal to k = 2.

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
Explanation : subarrays [1,2] and [3] have sum equal to k = 3.

Let’s Understand the Problem

As input we have been given an integer array nums and a target k. Then we are simply asked to find the number of subarrays whose sum will be k.

In case you do not recall what a subarray is! 😉

A subarray is a sequence of elements from an array that is continuous, meaning the elements must appear in the same order and without skipping any elements.

For example, if the array is nums = [1, 2, 3, 4], its possible subarrays include:

Single-element subarrays: [1], [2], [3], [4]

Two-element subarrays: [1, 2], [2, 3], [3, 4]

Three-element subarrays: [1, 2, 3], [2, 3, 4]

The entire array: [1, 2, 3, 4]

However, [1, 3] or [2, 4] would not be subarrays because they skip elements and break the contiguous sequence.

1. A very Brut-ish Approach

The devil’s mind is always tempted to take the easy way. Hey why not just find all the subarrays, check their sums. And tada we have our answer.

The Approach

We first use two loops to iterate over the given array to find all subarrays {i, j}, and then accumulate the elements from i to j. Finally maintain a count variable and increment it when the sum of subarray equals k.

Implementation Code

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
       
        // Step I : Find all subarrays by iterating through the array
        for (int start = 0; start < nums.length; start++) {
            for (int end = start; end < nums.length; end++) {
                int sum = 0;

                // Step II: Calculate the sum of the current subarray
                for (int i = start; i <= end; i++) {
                    sum += nums[i];
                }

                // Step III: Check if the sum equals k
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

Time Complexity : O(n³)

Explanation: Three nested loops iterate over all possible subarrays and calculate their sums.

Space Complexity : O(1)

Explanation: No extra space is used.

2. Optimized Brute Force Method

The Smarter Way

One thing we do realize when learning math is that, when adding numbers like 1,2,3,4,….

We do not add 1+2 =3, then 1+2+3=6 and 1+2+3+4=10

But we do it on the go to avoid repetition:

1+2 =3 => 3+3=6 => 6+4=10

And the same applies here as well, instead of starting fresh every time with a new subarray, you just keep adding numbers as you go.

Approach

We calculate the sum of the subarray {0, i} (denoted as sum_i) and the sum of the subarray {0, j} (denoted as sum_j), the sum of the subarray {i, j} can be expressed as:
sum of subarray (i, j) = sum_j - sum_i + nums[i], where 0 <= i <= j < n.

Implementation Code

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        
        // Step I: Iterate through the array
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;

            // Step II: Accumulate the sum for subarrays starting from 'start'
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

Time Complexity : O(n²)

Explanation: Two nested loops iterate over all possible subarrays and calculate their sums.

Space Complexity : O(1)

Explanation: No extra space is used.

Why does TLE occur at this point?

Often people have a common question at this point, why my code still gives TLE(Time Limit Exceeded) error, even though I have already optimized my code once.

If you were to look at the constrains on the size of array for once given in the problem : 1 <= nums.length <= 2 x 10^4 .

With a constraint of nums.length <= 20,000, an O(n²) solution, where n is the size of the array) would require up to 400 million operations in the worst case, which is too slow for modern time limits, typically set to run in under 1–2 seconds.

This results in Time Limit Exceeded (TLE) because the algorithm exceeds the time limits for large inputs.

A FAILED STRATEGY — SLIDING WINDOW

Its only right we give everyone chance and so I wondered how about using sliding window. And we have all seen the sliding window technique being often used to find contiguous subarrays that satisfy a certain condition. I mean isn’t it quite close to what we want.

Why Sliding Window Fails: [ASK YOURSELF 🤔]

THE REASON — In this problem, the sliding window technique fails due to the presence of negative numbers in the array.

Again through the constraints of the problem we know that our given input array might contain negative elements: -1000 <= nums[i] <= 1000

Explanation : Consider the array [1, 2, -3, 1, 2, -3] with k = 0.

The sliding window might identify two subarrays [1, 2, -3] and [1, 2, -3] separately, both summing to 0. However, it will miss the subarray that spans the entire array, which also sums to 0.

This happens because the sliding window technique typically expands the window to the right, but once a negative element is encountered, the window might exclude parts of the array that sum to k.

Thus, the sliding window doesn’t work here because it can’t backtrack or include necessary elements from the left side once it moves forward, making it unsuitable for arrays with negative numbers.

A small quiz to you to find the optimal strategy

In the above solution we used an expression:

sum of subarray (i, j) = sum_j — sum_i + nums[i]

where, sum_j and sum_i are sum of subarray ranging from (0,j) and (0,i).

In fact they are prefix sums.

And in fact the condition check :

sum of subarray (i,j) = pre[j] — pre[i] == k

Does the expression looks familiar to you : pre[j] — pre[i] == k

Have you seen it before?

You guessed it right! It is the first question of LeetCode, the sum of two numbers! (Two sum problem)

Recall that the sum of two numbers requires us to find all the cases where nums[i] + nums[j] == k (the logic is the same whether it is addition or subtraction), and the brute force method is the same . What method did we use to optimize it?

Yes! It is a HashMap!

That’s our secret ingredient.

Thinking of this, the optimization logic of this question is actually clear.

Optimized Solution 👑

TRUTHS & FACTS

1. ) Prefix Sum Concept — If the prefix sum at two points(indexes) are same that means the sum lying between those two indexes is zero.

Example: Consider an array: [3, -1, 2, -2, 1] We compute the prefix sum for each element:

Now, if we compare prefix sums:

• At index 0: Prefix sum = 3
• At index 3: Prefix sum = 2

The prefix sum at index 0 and index 3 are not the same, but if we check the sum between index 1 and 3

prefix sum at index 3 - prefix sum at index 1 = 2–2 = 0

it shows that the sum between these indexes is zero.

2.) Difference in Prefix Sum Equals k — If the prefix sum at two indexes(i and j) is at a difference of k. prefixsum[j] — prefixsum[i]=k; That means the sum of elements lying between the two indexes is k.

Example: Consider the same array: [3, -1, 2, -2, 1]

Suppose we want to find the sum between index 1 and 4:

• Prefix sum at index 4 = 3
• Prefix sum at index 1 = 2

The difference between the prefix sums at these two indexes is 3 - 2 = 1, which means the sum of elements between these indexes is 1.

Approach

To reach the solution we first need to find all pairs where pre[j] - pre[i] == k (where 0 <= i <= j < n). The brute force approach would check each pair (i, j) in the range 0 <= i <= j < n, which takes O(n^2) time. However, we can improve this by using a hashmap to store the values of prefix[i] as we traverse prefix[j]. This allows us to quickly check if pre[j] - k exists in the hashmap or not, reducing the time complexity.

Further, for every sum encountered, we also determine the number of times the sum sum−k has occurred already, since it will determine the number of times a subarray with sum k has occurred up to the current index.

Steps

Step 1: Initialize a HashMap with (0, 1) to handle base cases.
Step 2: Traverse through the array, updating the prefix sum and checking if sum - k exists in the map, adding the count of valid subarrays.
Step 3: Update the map with the current prefix sum's frequency and return the total count of valid subarrays.

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int count = 0;
        int sum = 0;
        for (int num : nums) {
            // Step I: // Update the prefix sum
            sum += num; 

            // Step II: Check if (sum - k) exists in the map
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }

            // Step III: Add the current sum to the map (increment the frequency)
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

Time Complexity : O(n)

Explanation: We iterate through the array once, and each HashMap operation (lookup and update) takes constant time.

Space Complexity : O(n)

Explanation: The space complexity is determined by the HashMap, which can store up to n different prefix sums in the worst case.

DO THIS OR I WILL BE SAD 🥺

Solve a similar question to further deepen your understanding with the concepts we have discussed above. I am sure they will come handy in many questions. Here are some questions of similar nature and understanding:

523. Continuous Subarray Sum

930. Binary Subarrays With Sum

Follow me on medium to get notification for all my amazing LeetCode editorials.

Find my other leetcode solution on my github — https://github.com/Harshit-Raj-14/My-Leetcode-Solutions . (Follow me and star mark the repo)

Best of Luck!

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

If you got to learn something valuable from this article and clap and follow me if you found it helpful.

Follow me for more such awesome articles that can help you in your interview preparation and studies and learn coding.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, tutorials, Coding Question solutions Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

“This Method Quickly Cured My Procrastination” — The Scientific Trick

Checkout the article now — Click here

In this blog, I would be discussing this question with different approaches which you would come up in an interview in the manner of increasing difficulty. I will be writing this post in such a way as if I were the person being interviewed. So, enjoy 😊

Problem Statement:

Interviewer : Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Brute Force Approach

Interviewee: Absolutely, let’s start with the fundamentals. The brute force approach involves looping through the array, excluding the current element, and multiplying the rest. While simple, its time complexity is O(n²).

// Java code for brute force approach
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            int pro = 1;
            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                pro *= nums[j];
            }
            ans[i] = pro;
        }
        
        return ans;
    }
}

Interviewer: Indeed, an essential starting point. Now, let’s optimize.

Dividing the Product of Array with the Number

Interviewee: Right, here we calculate the product of all elements and divide by each element to obtain the desired result. However, we face challenges when encountering zeroes in the array due to division by zero.

// Java code for dividing the product of array with the number
class Solution {
    public int[] productExceptSelf(int[] nums) {
                int n = nums.length;
        int countZeroes = 0;
        int indexZero = -1;
        int productWithoutZero = 1;
        for(int i = 0 ; i < n ; i++) {
            if(nums[i] == 0) {
                countZeroes++;
                indexZero = i;
            }
            else productWithoutZero *= nums[i];
        }    
        int [] output = new int [n];
        if(countZeroes == 0) {
            for(int i = 0 ; i < n ; i++) {
                output[i] = productWithoutZero / nums[i];
            }
        }
        else if(countZeroes == 1) {
            output[indexZero] = productWithoutZero;
        }
        return output;
    }
}

LOGIC — -
maintain the count of zeroes in the array.
1.) If count of zeroes is greater than 1 so the array will be empty
2.) If the count of zeroes is 0 then we need to just divide the product of array with every element
3.) Lastly if the count of zeroes if 1, then we need to find the index of zero and product of array without zero and then just place the product at index of zero and we are done

Note — What if there is more than one zero??
ans: read point no 1

Finding Prefix Product and Suffix Product

Interviewee: Similar to finding prefix sums, we compute prefix and suffix product arrays. Then, the final answer at each index is the product of its prefix and suffix, excluding the element itself. This approach offers a time complexity of O(n) but uses additional space.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int prefix[] = new int[nums.length];
        prefix[0]=1; 
        for(int i=1;i<nums.length;i++){
            prefix[i]=prefix[i-1]*nums[i-1];
        }
        int suffix[] = new int[nums.length];
        suffix[nums.length-1]=1; 
        for(int i=nums.length-2;i>=0;i--){
            suffix[i]=suffix[i+1]*nums[i+1];
        }
        int ans[] = new int[nums.length];
        for(int i=0;i<nums.length;i++) ans[i]=prefix[i]*suffix[i];
        return ans;
    }
}

LOGIC — -
For any nums[i], calculate its left product and calculate its right product, without including nums[i] as prefix and suffix.
Then multiply these left and right product, This will give product of array excluding nums[i].

Interviewer: Excellent! Now, let’s optimize space.

Directly Store the Product of Prefix and Suffix into the Final Answer Array

Interviewee: Precisely, we can perform the same calculations directly onto our final answer array, minimizing auxiliary space to O(1).

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        Arrays.fill(ans, 1);
        for(int i = 1; i < n; i++) {
            ans[i] = ans[i-1] * nums[i-1];
        }
        int curr = 1;
        for(int i = n - 1; i >= 0; i--) {
            ans[i] *= curr;
            curr *= nums[i];
        }
        return ans;
    }
}

Interviewer: Well done! These approaches showcase your problem-solving skills impressively. Thank you for sharing your insights.

Interviewee: Thank you for the opportunity. It’s been a pleasure discussing these strategies with you.

DO THIS OR I WILL BE SAD 🥺

Do ask in comments if you face any problem in the above solutions. If the prefix and suffix part is not clear to you, my suggestion is to revise or learn these topics thoroughly.

Follow me on medium to get notification for all my amazing LeetCode editorials.

Find my other leetcode solution on my github — https://github.com/Harshit-Raj-14/My-Leetcode-Solutions . (Follow me and star mark the repo)

Best of Luck!

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

If you got to learn something valuable from this article and clap and follow me if you found it helpful.

You can encourage me to write more such articles on: https://ko-fi.com/medusaverse

Follow me for more such awesome articles that can help you in your interview preparation and studies and learn coding.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, tutorials, Coding Question solutions Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

“This Method Quickly Cured My Procrastination” — The Scientific Trick

Checkout the article now — Click here

Quiz #1: What Are APIs?

Q1) What is an API? Pick the best answer from one of the choices below.

(a) A file format for images

(b) Apple’s new iPhone programming language

© A contract that allows code to talk to other code.

(d) A unit used for storage measurement

Answer : (c) A contract that allows code to talk to other code.

Q2) What are some different types of APIs?

(1) REST APIs

(2) GraphQL

(3) gRPC

(4) ElectricSockets

Answer : (1) REST APIs, (2) GraphQL, (3) gRPC

Quiz #2 Introducing Postman

Q1) Postman has a vision for an API-First World. In the API-first world:

(1) APIs are considered a #1 priority

(2) APIs will make you famous on TikTok

(3) APIs are easily consumable

(4) API stands for Application Postman Interface

(5) APIs are easily discoverable

Answer : (1), (3), (5)

Quiz #3: Your First API Request

Q1) You are given three blocks of text (see image below). Each block is part of a request URL. Which of the answer choices below lists these parts in the correct order?

https:// library-api.postman.labs.com /books

(1) path, host, protocol

(2) protocol, host, proxy

(3) host, proxy, path

(4) protocol, host, path

Answer : (4) protocol, host, path

Q 2) You are given a table of response status codes (see image below). Using only the code ranges given, choose the answer that lists the correct order of meanings for the codes that are given, starting at "2xx".

Code Range 2xx 3xx 4xx 5xx

(1) Redirection, Success, Client Error, Redirection, Server Error

(2) Success, Redirection, Server Error, Client Error

(3) Server Error, Success, Redirection, Client Error

(4) Success, Client Error, Redirection, Server Error

(5) Success, Redirection, Client Error, Server Error

Answer : (4) protocol, host, path

Quiz #4: Query vs. path parameters

Q 1) What type of parameter is :id below?

GET https://api.some-url.com/books/:id

(1) query parameter

(2) path parameter

Answer : (2) path parameter

Q 2) How many query parameters are present in this request URL?

GET https:/library-api.postmanlabs.com/books?genre=fiction&search=borges

(1) 1

(2) 0

(3) 2

(4) 3

Answer : (3) 2

Q3) How many path parameters are in this documented endpoint?

GET https://library-api.postmanlabs.com/books

(1) 1

(2) 0

Answer : (2) 0

Quiz #5: Sending Data With Postman

Q1) What could happen if you don't include Authorization (aka Auth) to your API? Select all answers that apply.

(1) Your computer can explode

(2) Your API will have completely open endpoints that anyone can access publicly

(3) Unauthorized people will be able to access data they shouldn't see

(4) Bots would be able to flood an API with thousands of calls per second and shut it down.

Answer : (2), (3), (4)

Q2)You send this request in Postman and get this response code: 401. What is the error here?

{
   "title": "To Kill a Mockingbird",
   "author": "Harper Lee",
   "genre": "fiction",
   "yearPublished": 1960
}

(1) the path changed

(2) there is not enough storage space in the server

(3) there are no issues

(4) the request needs authorization

Answer : (4) the request needs authorization

Quiz #6: Intro to Variables

Q1) Choose all the answers that apply. Postman allows you to save values as variables so that you can:

(1) Spend more time reading the API-First World!

(2) Reuse values to keep your work DRY (Don’t Repeat Yourself)

(3) Cool off your computer

(4) Hide sensitive values like API keys from being shared publicly

Answer : (2), (4)

DO THIS OR I WILL BE SAD 🥺

It would be great if you can also share some good problems in the comments to help others and check your knowledge based on questions asked by others.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe

Question 1
True or false? C# is similar to C, C++, Java and JavaScript. Select the best answer.
a) True
b) False

Answer: a) True

Question 2
True or false? Pascal case is used when naming a class, record or struct. Select the best answer.
a) True
b) False

Answer: a) True

Question 3
True or false. Coding conventions make developers focus more on layout. Select the best answer.
a) True
b) False

Answer: b) False

Question 4
When naming a private or internal field, which naming convention should you use?
a) All caps
b) Snake case
c) Pascal case
d) Camel case

Answer: d) Camel case

Question 5
Which script provides an excellent way of easily managing things that need to happen after a delay or over the course of time? Select the best answer.
a) Force
b) IF statement
c) Torque
d) Coroutine

Answer: d) Coroutine

Question 6
What are some of the useful features in the Unity Manual that you could use? Select all that apply.
a) An index that allows you to search by topic
b) A button to switch between a specific topic in Unity Manual and Scripting API library
c) Sample game design documents that you can use as templates
d) Ability to copy code samples

Answer: a) An index that allows you to search by topic, b) A button to switch between a specific topic in Unity Manual and Scripting API library, d) Ability to copy code samples

Question 7
In which window can you attach a script to a GameObject?
a) Hierarchy
b) Scene
c) Game
d) Inspector

Answer: d) Inspector

Question 8
True or false? The component name, the class and the filename of the script should all have the same name. Select the best answer.
a) True
b) False

Answer: a) True

Question 9
How do you enable or disable a component in Unity? Select the best answer.
a) Use the enabled flag.
b) Use the Remove flag.
c) Use the Escape button.
d) Use the Destroy function.

Answer: a) Use the enabled flag.

Question 10
A click on a Collider or a GUI text element is detected by which function?
a) OnCollision
b) OnClick
c) OnDetect
d) OnMouseDown

Answer: d) OnMouseDown

DO THIS OR I WILL BE SAD 🥺

It would be great if you can also share some good problems in the comments to help others and check your knowledge based on questions asked by others.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe

Question 1: What is the first step in the asset workflow process?

Answer: Import

Question 2: Which step in the asset workflow refers to adding assets into the Unity Editor? Select the best answer.

a. Load

b. Import

c. Build

d. Distribute

Answer: b. Import

Question 3: Which step in the asset workflow process involves giving users access to built files?

Answer: Distribute

Question 4: Screen size is a type of asset used in Unity.

a. True

b. False

Answer: b. False

Question 5: When importing assets into Unity, where can you right-click to begin the importing assets process? Select the best answer.

a. Script

b. Project window

c. Update() method field

d. Vector3 field

Answer: b. Project window

Question 6: Which tool in Unity helps you in relocating the position of your camera? Select the best answer.

a. Hand tool

b. Move tool

c. Scale tool

d. Rect tool

Answer: b. Move tool

Question 7: Which axes are used for adjusting the position of your camera in Unity? Select the best answer.

a. 1st, 2nd, and 3rd axes

b. A, B, and C axes

c. Left, right, and center axes

d. X, Y, and Z axes

Answer: d. X, Y, and Z axes

Question 8: What component can you add to 3D objects in Unity to simulate physics?

a. RigidBody

b. Collision

c. ReactionDev

d. Outer mesh

Answer: a. RigidBody

Question 9: Which of the following is the best way to name a script in Unity? Select the best answer.

a. follow player

b. followplayer

c. FollowPlayer

d. _follow_player

Answer: c. FollowPlayer

Question 10: The LateUpdate() method overrides the Update() method.

a. True

b. False

Answer: b. False

DO THIS OR I WILL BE SAD 🥺

It would be great if you can also share some good problems in the comments to help others and check your knowledge based on questions asked by others.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe

1. True or false: App-based AR provides users with an AR experience that takes advantage of the device’s hardware.

a) True

b) False

Answer: a) True

2. What is the goal of real-time software? Select the best answer.

a) To give users ample time to see what they created

b) To render images so quickly that users won’t notice delays

c) To limit the number of new ideas

d) To increase the number of iterations

Answer: b) To render images so quickly that users won’t notice delays

3. True or false: Unity has free personal licensing to show content to under 100,000 users.

a) True

b) False

Answer: a) True

4. True or false: The Scene view in the Unity Editor provides an interactive view into the world you are creating.

a) True

b) False

Answer: a) True

5. Which type of document in the pre-production phase of the production cycle defines the scope of what you’re going to create? Select the best answer.

a) Design document

b) Storyboard

c) Project plan

d) Project charter

Answer: d) Design document

6. True or false: A project plan is used to manage a project’s progress and schedule.

a) True

b) False

Answer: a) True

7. What type of questions should you be prepared to answer in an interview?

Answer:

8. True or false: You should include narrative introductions to each project in your portfolio.

a) True

b) False

Answer: a) True

9. What is a tool developers commonly use to showcase their work? Select the best answer.

a) MicrosoftⓇ OneDrive

b) Google Drive

c) GitHub

d) Dropbox

Answer: c) GitHub

10. What is a package in Unity? Select the best answer.

a) A package in Unity is a tool used for 3D development.

b) A package in Unity is a grouping of code.

c) A package in Unity is a collection of platform-specific subsystems.

d) A package in Unity is a container that stores various types of features or assets.

Answer: d) A package in Unity is a container that stores various types of features or assets.

11. What is the difference between app-based AR and web AR? Select the best answer.
a. Web AR allows for more complex content and higher definition.
b. With app-based AR, the user runs a web-based application in the browser on their mobile device.
c. App-based AR provides access to limited hardware, which allows for simpler content and assets.
d. App-based AR requires the user to download an app, while web AR runs web-based applications in a browser on their mobile device.

Answer: App-based AR requires the user to download an app, while web AR runs web-based applications in a browser on their mobile device.

12. Which type of rendering allows users to interact with a project without any noticeable delay? Select the best answer.
a. Interactive
b. Real-time
c. Non-interactive
d. Offline

Answer: Real-time

13. Which window in the Unity Editor do you use to view and create your 3D world?
a. Hierarchy window
b. Project window
c. Scene window
d. Inspector window

Answer: Scene window

14. At which point in a project should design documents be created? Select the best answer.
a. During the post-production phase
b. During the production phase
c. During the client review phase
d. During the pre-production phase

Answer: During the pre-production phase

15. Which document is used to manage a project’s progress and schedule? Select the best answer.
a. Game design document
b. Project charter
c. Project plan
d. Design document

Answer: Project plan

16. True or false: Technical questions in an interview may include inquiries into your knowledge of product features such as AR Session, AR Core, AR Kit, and AR Foundation in Unity.
a. True
b. False

Answer: True

17. What elements should be included in a portfolio? Select all that apply.
a. A download option for the portfolio items
b. An overview of your skills and the projects included in the portfolio
c. Narrative introductions to each project
d. Date of birth and ethnicity

Answer: An overview of your skills and the projects included in the portfolio, Narrative introductions to each project.

18. What does GitHub allow you to do?
a. Manage project progress
b. Collaborate on software development projects
c. Create 3D worlds
d. Showcase AR content

Answer: Collaborate on software development projects

DO THIS OR I WILL BE SAD 🥺

It would be great if you can also share some good problems in the comments to help others and check your knowledge based on questions asked by others.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe

Q1) What is an example of both a generative AI model and a discriminative AI model?

(a) A generative AI model could be trained on a dataset of images of cats and then used to classify new images of cats. A discriminative AI model could be trained on a dataset of images of cats and dogs and then used to predict new images as either cats or dogs.

(b) A generative AI model does not need to be trained on a dataset of images of cats and then used to generate new images of cats, because the images were already generated by using AI. A discriminative AI model could be trained on a dataset of images of cats and dogs and then used to classify new images as either cats or dogs.

(c) A generative AI model could be trained on a dataset of images of cats and then used to generate new images of cats. A discriminative AI model could be trained on a dataset of images of cats and dogs and then used to classify new images as either cats or dogs.

(d) A generative AI model could be trained on a dataset of images of cats and then used to cluster images of cats. A discriminative AI model could be trained on a dataset of images of cats and dogs and then used to predict as either cats or dogs.

Correct Answer!

A generative AI model could be trained on a dataset of images of cats and then used to generate new images of cats. A discriminative AI model could be trained on a dataset of images of cats and dogs and then used to classify new images as either cats or dogs.

Q2) What is a prompt?

(1) A prompt is a short piece of text that is given to the large language model as input, and it can be used to control the output of the model in many ways.

(2) A prompt is a short piece of text that is given to the small language model (SLM) as input, and it can be used to control the output of the model in many ways.

(3) A prompt is a short piece of code that is given to the large language model as input, and it can be used to control the output of the model in many ways.

(4) A prompt is a long piece of text that is given to the large language model as input, and it cannot be used to control the output of the model.

(5) A prompt is a short piece of text that is given to the large language model as input, and it can be used to control the input of the model in many ways.

Correct Answer

A prompt is a short piece of text that is given to the large language model as input, and it can be used to control the output of the model in many ways.

Q3. What is Generative AI?

Generative AI is a type of artificial intelligence (AI) that can create new content, such as discrete numbers, classes, and probabilities. It does this by learning from existing data and then using that knowledge to generate new and unique outputs.

Generative AI is a type of artificial intelligence (AI) that can create new content, such as text, images, audio, and video. It does this by learning from existing data and then using that knowledge to generate new and unique outputs.

Generative AI is a type of artificial intelligence (AI) that can only create new content, such as text, images, audio, and video by learning from new data and then using that knowledge to predict a discrete, supervised learning output.

Generative AI is a type of artificial intelligence (AI) that can only create new content, such as text, images, audio, and video by learning from new data and then using that knowledge to predict a classification output.

Correct Answer

Generative AI is a type of artificial intelligence (AI) that can create new content, such as text, images, audio, and video. It does this by learning from existing data and then using that knowledge to generate new and unique outputs.

Q4) What are foundation models in Generative AI?

A foundation model is a large AI model both post and pre-trained on a vast quantity of data that was “designed to be adapted” (or fine-tuned) to a wide range of downstream tasks, such as sentiment analysis, image captioning, and object recognition.

A foundation model is a large AI model post-trained on a vast quantity of data that was “designed to be adapted” (or fine-tuned) to a wide range of downstream tasks, such as sentiment analysis, image captioning, and object recognition.

A foundation model is a large AI model pretrained on a vast quantity of data that was “designed to be adapted” (or fine-tuned) to a wide range of upstream tasks, such as sentiment analysis, image captioning, and object recognition.

A foundation model is a small AI model pretrained on a small quantity of data that was “designed to be adapted” (or fine-tuned) to a wide range of downstream tasks, such as sentiment analysis, image captioning, and object recognition.

A foundation model is a large AI model pretrained on a vast quantity of data that was “designed to be adapted” (or fine-tuned) to a wide range of downstream tasks, such as sentiment analysis, image captioning, and object recognition.

Correct Answer!

A foundation model is a large AI model pre-trained on a vast quantity of data that is “designed to be adapted” (or fine-tuned) to a wide range of downstream tasks, such as sentiment analysis, image captioning, and object recognition.

Q5) Hallucinations are words or phrases that are generated by the model that are often nonsensical or grammatically incorrect.

What are some factors that can cause hallucinations? Select three options.

The model is trained on too much data.

The model is not given enough context.

The model is not trained on enough data

The model is trained on noisy or dirty data.

Correct Answer

1. The model is not given enough context.
2. The model is trained on noisy or dirty data.
3. The model is not trained on enough data.

DO THIS OR I WILL BE SAD 🥺

It would be great if you can also share some good problems in the comments to help others and check your knowledge based on questions asked by others.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe

Welcome to the editorial for Starters 104.

Double Rent

import java.util.*;
class Codechef{
 public static void main (String[] args){
  Scanner sc = new Scanner(System.in);
  int n=sc.nextInt();
  System.out.println(2*n);
 }
}

Pizza Cutting

import java.util.*;
class Codechef{
 public static void main (String[] args){
  Scanner sc = new Scanner(System.in);
  int t=sc.nextInt();
  while(t-->0){
      int n=sc.nextInt();
      int possible=0;
      if(n==1 || n%2==0) possible=1;
      if(possible==1) System.out.println("YES");
      else System.out.println("NO");
  }
 }
}

Santa and Chocolates

import java.util.*;
class Codechef{
 public static void main (String[] args){
  Scanner sc = new Scanner(System.in);
  int t=sc.nextInt();
  while(t-->0){
      int n=sc.nextInt(); //no of children
      int k=sc.nextInt(); //difference of choclates atmost
      int sum=0;
      int arr[] = new int[n];
      for(int i=0;i<n;i++){
          arr[i]=sc.nextInt();
          sum+=arr[i];
      }
      if(n>sum) System.out.println("NO");
      else if(sum%n==0) System.out.println("YES");
      else{
          int val=0;
          //distribute first everyone equal
          int left = sum%n;
          int equal=sum-left; //let this be groudn state=0;
          int ans[] = new int[n];
          int index=0;
          while(left!=0){
              if(index>=n) index=0;
              ans[index]++;
              index++;
              left--;
          }
          if(ans[0]-ans[n-1]>k) System.out.println("NO");
          else System.out.println("YES");
      }
  }
 }
}

LOGIC — -

Objective : to distribute the candies in such a way that the atmost difference between any two children is k.

Case I: n>sum => no of children more than number of candies => failed
As each child need to have atleast one candy

Case II : sum%n==0 => each child can have sum/n candies with difference 0

Case III: sum>n => A general case
First we try to say we distributed equal candies to all that is : equal= sum — (sum%n)
So, left candies = sum%n
Now we try to distribute these candies in loop
The max difference will exist between first element and last element
If that difference is greater than k we fail otherwise pass

GCD and LCM

Method I : O(k log(n))

import java.util.*;
class Codechef{
 public static void main (String[] args){
  Scanner sc = new Scanner(System.in);
  int t=sc.nextInt();
  while(t-->0){
      int x=sc.nextInt(); 
      int y=sc.nextInt();
      int k=sc.nextInt();
      int equal=0;
      while(k-->0 && equal==0){
          if(x==y){
              equal=1;
              continue;
          }
          //first step
          int gd=gcd(x,y);
          if(x>=y) x=gd;
          else y=gd;
          //second step
          int lc=(x*y)/gd;    //LCM x HCF = one number x other number
          if(x>=y) x=lc;
          else y=lc;
      }
      System.out.println(x+y);
  }
 }
 
 public static int gcd(int a, int b){
     if (b == 0) return a;
     if(a==b) return a;
        else return gcd(b, a % b);
    }   
}

LOGIC — -

Just do what the question says

Observations :
If x and y are same (x==y) no matter how many operations you apply : final sum = x+y

Otherwise, perform the steps :
Everytime you find gcd or lcm replace it with the largest element
Continue to apply operation k times

Method II: O(log (n))

import java.util.*;
class Codechef{
 public static void main (String[] args){
  Scanner sc = new Scanner(System.in);
  int t=sc.nextInt();
  while(t-->0){
      int x=sc.nextInt(); 
      int y=sc.nextInt();
      int k=sc.nextInt();
      int g=gcd(x,y);
      int sum=0;
      if (k <= 1) sum = g + Math.min(x, y);
      else sum=2*g;
      System.out.println(sum);
  }
 }
 
 public static int gcd(int a, int b){
     if (b == 0) return a;
     if(a==b) return a;
        else return gcd(b, a % b);
    }
}

LOGIC — -

Case I : k=0,1
First apply GCD
(X,Y) => (g, y) => for sure now that g is a factor of y and y<x
Now if you apply lcm on (g,y) => you still get y only because g is a factor of y => since g<y, let’s make y lcm which is y again
sum = g+y = g + min(x,y)

Case II: k>1
In next step we again apply gcd again getting g and this time replacing y with g
Now we have x=g, y=g
Two equal number meaning
lcm = g
No matter how many times k you apply => max sum=2^g

Maximise Sum

import java.util.*;
class Codechef{
 public static void main (String[] args){
  Scanner sc = new Scanner(System.in);
  int t=sc.nextInt();
  while(t-->0){
      int n=sc.nextInt();
      int arr[] = new int[n];
      int sorted=1;
      int sum=0;
      for(int i=0;i<n;i++){
          arr[i]=sc.nextInt();
          sum+=arr[i];
          if(i>0 && arr[i]<arr[i-1]) sorted=0; 
      }
      if(sorted==1) System.out.println(sum);
      else{
          int greatL[] = new int[n];
          greatL[0]=arr[0];
          int greatR[] = new int[n];
          greatR[n-1]=arr[n-1];
          for(int i=1;i<n;i++){
              if(greatL[i-1]>arr[i]) greatL[i]=greatL[i-1];
              else greatL[i]=arr[i];
          }
          for(int i=n-2;i>=0;i--){
              if(greatR[i+1]>arr[i]) greatR[i]=greatR[i+1];
              else greatR[i]=arr[i];
          }
          long sum2=arr[0]+arr[n-1];
          for(int i=1;i<n-1;i++){
              arr[i]=Math.max(arr[i], Math.min(greatL[i], greatR[i]));
              sum2+=arr[i];
          }
          System.out.println(sum2);
      }
  }
 }
}

LOGIC — -

Observation:
Case I: sorted
If array is sorted or all elements equal => you shouldn’t apply the operation as it will never help to increase the value.
In such case just output their sum.

Case II: Unsorted
We cannot apply operation on first and last element.
Calculate for each index in between the max great on their left and max great on their right.
This will help to decide to pick which element form left or right if we want an exchange.
Now check if element is less than the greatL and greatR. Now pick the smaller of the two and apply the operation.

Now calculate sum finally.

Lexicographically Largest

import java.util.*;
class Codechef{
 public static void main (String[] args){
  Scanner sc = new Scanner(System.in);
  int t=sc.nextInt();
  while(t-->0){
      int n=sc.nextInt();
      int m=sc.nextInt(); //upperbound
      int arr[] = new int[n];
      for(int i=0;i<n;i++){
          arr[i]=sc.nextInt();
      }
      int b[] = new int[n];
      b[0]=arr[0];
      for(int i=1;i<n;i++){
          b[i]=solve(arr[i], m, arr[i-1]);
      }
      for(int i=0;i<n;i++){
          System.out.print(b[i]+" ");
      }
      System.out.println();
  }
 }
 
 public static int solve(int gcd, int m, int prevgcd){
     int num=m/gcd;
     num*=gcd;
     for(int i=x;i>=1;i-=gcd){ //we iterate backwards to get the largest value first
         if((i%gcd==0)){
             if(GCD(prevgcd, i)==gcd) return i;
         }
     }
     return 1;
 }
 
 public static int GCD(int a, int b){
     if (b == 0) return a;
     if(a==b) return a;
        else return GCD(b, a % b);
    }
}

LOGIC — -

Conclusion: a[0] = gcd(b[0]) = b[0]

How?
a[i] = gcd(b[0], b[1],…. b[i])
=> a[i] = gcd(gcd(b[0], b[1],…b[i-1]), b[i])
=> a[i] = gcd(a[i-1], b[i])
Now since we have got an upper bound for b as m
We check which is the largest possible element by checking from 1->m for each b[i] since we already know a’s
Now calculate max sum

If you understood brute force till now,
We will add the magic step.

We need to find the largest number that is num<=m , such that gcd (num ,a[i-1])=a[i].
So we find the maximum number which is <=m and a[i] is a factor.
something like num=m/a[i];
now even if num is not a multiple of a[i], we just again multiply with a[i] to make it.
num*=a[i]
Now we iterate from num to 1 and check which value
To reduce the number of iterations we know that the next gcd fulfilling value will only exist, when each step is reduced by gcd itself.

LINK TO CODES

All the codes are available on my GitHub repo — repo link

DO THIS OR I WILL BE SAD 🥺

It would be great if you can also share your explanation with us if you did something different and would consider it worth sharing otherwise best of luck solving these problems.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe

Interviewer: Prove to me that you’re smart.

Candidate: Oh, that’s quite easy. I can even make you admit I’m smart.

Interviewer: How?

Candidate: Consider this: There are just the two of us here. One of us must be more intelligent than the other. I’m here to apply for a job, and you’re conducting the interview from across the table. If I were the smarter one, I would be sitting in your chair, and you would be sitting in mine. The fact that you’re interviewing me shows that you’re the smarter one. What does that say about me?

Interviewer: You’re smart.

Candidate: 😎.

Verdict — Selected.

Why the interviewer asked this question:

The interviewer posed this question to assess the candidate’s intelligence or cleverness. By asking, “Prove to me that you’re smart,” the interviewer wanted to gauge the candidate’s ability to think on their feet and display their problem-solving skills.

This question also allowed the interviewer to see how the candidate approached a somewhat tricky situation and presented their thoughts logically.

The interviewer might have been looking for creativity and confidence in the candidate’s response, as well as the ability to make a convincing argument. Ultimately, this question was a way to evaluate the candidate’s critical thinking and communication skills, which are often important qualities for the job.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below social links.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe