truck tour hackerrank solution javascript

Programmingoneonone - Programs for Everyone

• HackerRank Problems Solutions
• _C solutions
• _C++ Solutions
• _Java Solutions
• _Python Solutions
• _Interview Preparation kit
• _1 Week Solutions
• _1 Month Solutions
• _3 Month Solutions
• _30 Days of Code
• _10 Days of JS
• CS Subjects
• _IoT Tutorials
• DSA Tutorials
• Interview Questions

HackerRank Truck Tour problem solution

In this HackerRank Truck Tour problem, we have given the number of petrol pumps and the distance between each petrol pump, and the amount of petrol at every petrol. we just need to find the smallest index of the petrol pump from which we can start the tour.

Problem solution in Python programming.

Problem solution in java programming., problem solution in c++ programming., problem solution in c programming., problem solution in javascript programming..

Posted by: YASH PAL

You may like these posts, post a comment.

• 10 day of javascript
• 10 days of statistics
• 30 days of code
• Codechef Solutions
• coding problems
• data structure
• hackerrank solutions
• interview prepration kit
• linux shell

Social Plugin

Subscribe us, popular posts.

HackerRank Highest Value Palindrome problem solution

HackerRank Equal Stacks problem solution

HackerRank Minimum Loss problem solution

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Queue Data Structure
• Introduction to Queue - Data Structure and Algorithm Tutorials
• Introduction and Array Implementation of Queue
• Queue - Linked List Implementation
• Applications, Advantages and Disadvantages of Queue
• Different Types of Queues and its Applications

Queue implementation in different languages

• Queue in C++ Standard Template Library (STL)
• Queue Interface In Java
• Queue in Python
• C# Queue with Examples
• Implementation of Queue in Javascript
• Queue in Go Language
• Queue in Scala

Some question related to Queue implementation

• Implementation of Deque using doubly linked list
• Queue using Stacks
• How to efficiently implement k Queues in a single array?
• Complete Tutorial on LRU Cache with Implementations

Easy problems on Queue

• Detect cycle in an undirected graph using BFS
• Breadth First Search or BFS for a Graph
• Traversing directory in Java using BFS
• Vertical order traversal of Binary Tree using Map
• Print Right View of a Binary Tree
• Find Minimum Depth of a Binary Tree
• Check whether a given graph is Bipartite or not

Intermediate problems on Queue

• Flatten a multilevel linked list
• Level with maximum number of nodes
• Find if there is a path between two vertices in a directed graph
• Print all nodes between two given levels in Binary Tree
• Find next right node of a given key
• Minimum steps to reach target by a Knight | Set 1
• Islands in a graph using BFS
• Level order traversal line by line | Set 3 (Using One Queue)
• Find the first non-repeating character from a stream of characters

Hard problems on Queue

• Sliding Window Maximum (Maximum of all subarrays of size K)
• Flood Fill Algorithm
• Minimum time required to rotten all oranges
• An Interesting Method to Generate Binary Numbers from 1 to n
• Maximum cost path from source node to destination node via at most K intermediate nodes
• Shortest distance between two cells in a matrix or grid
• Snake and Ladder Problem
• Minimum Cost of Simple Path between two nodes in a Directed and Weighted Graph
• Minimum Cost Path in a directed graph via given set of intermediate nodes

Find the first circular tour that visits all petrol pumps

Given information about N petrol pumps (say arr[] ) that are present in a circular path. The information consists of the distance of the next petrol pump from the current one (in arr[i][1] ) and the amount of petrol stored in that petrol pump (in arr[i][0] ). Consider a truck with infinite capacity that consumes 1 unit of petrol to travel 1 unit distance. The task is to find the index of the first starting point such that the truck can visit all the petrol pumps and come back to that starting point.

Note: Return -1 if no such tour exists.

Input: arr[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}}.  Output: 1 Explanation: If started from 1st index then a circular tour can be covered. Input: arr[] {{6, 4}, {3, 6}, {7, 3}} Output: 2

Naive Approach:

As the capacity of the truck is infinite it is feasible to fill the truck with all the amount of petrol available at each petrol pump.

A Simple Solution is to consider every petrol pumps as a starting point and see if there is a possible tour. If we find a starting point with a feasible solution, we return that starting point. 

Time Complexity: O(N 2 ) Auxiliary Space: O(1)

First Circular Tour Using Queue:

Instead of checking the whole array for each starting point, we can store the current tour inside a queue .  At the moment, the current amount of petrol becomes inefficient (i.e., negative) to reach the next petrol pump, remove the current starting point from the queue and consider the next point as the new starting point. Instead of building a separate queue, we can use the array itself as a queue with the help of start and end pointers. Note: Each petrol pump will be added in the queue at most twice and will be removed at most once.

Illustration:

Below image is a dry run of the above approach:

Follow the below steps to implement the idea:

• If the amount of petrol is efficient to reach the next petrol pump then increment the end pointer (circularly).
• Otherwise, remove the starting point of the current tour, i.e., increment the start pointer.
• If the start pointer reaches N then such a tour is not possible. Otherwise, return the starting point of the tour.

Below is the implementation of the above approach:

Time Complexity: O(N) Auxiliary Space: O(1)

First Circular Tour by checking only possible valid Starting Positions:

Another efficient solution can be to find out the first petrol pump where the amount of petrol is greater than or equal to the distance to be covered to reach the next petrol pump. 

Mark that petrol pump as start and check whether we can finish the journey towards the end point.  If in the middle, at any petrol pump, the amount of petrol is less than the distance to be covered to reach the next petrol pump, then we can say we cannot complete the circular tour from start .  Find the next start petrol pump where the amount of petrol is greater than or equal to the distance to be covered and we mark it as start . Continue this process till all points are visited or a starting point is found.

Let us discuss why we need not look at any petrol pump in between the initial petrol pump marked as start and the new start .

Let us consider there was a petrol pump at k th position between the old start and new start. This petrol pump will break the range into two parts. The case is that  both the parts can have negative sum,  the starting partition can have a negative sum or  the later half has a negative sum.  In the first and the last case we will not be able to reach the new start point.  And for the second case though we will be able to reach the new start but will not be able to complete the tour because we will not be able to cover some part in between 0 to the k th position. [As we already found that we could not reach to start from 0 and also we are not able to reach k from start . So the tour cannot be completed] 

Follow the steps mentioned below to implement the idea:

• Find the first possible petrol pump where the amount of petrol is greater than the distance to the next petrol pump.
• Traverse from i+1 to N and find the point where petrol is greater than the distance to the next petrol pump.
• Start from the new start point and continue the above procedure.
• Start from 0 to the found start point. If the sum of the petrol is non-negative then the start point is feasible otherwise not.

Below is the implementation of the above approach:  

First Circular Tour by using Single Loop:

The idea is similar to the above approach. 

Here we will use another variable to substitute the extra loop from start till the latest found start point. The variable will store the sum of utilized petrol from 0 till the latest start petrol pump.

Below is the implementation of the above approach: 

Time Complexity: O(N) Auxiliary Space: O(1) 

First Circular Tour using dynamic programming

In this approach first, we will storing the difference between petrol and distance then prefix array will store the difference of petrol and distance till the i’th position and suffix array will do the same from end. The idea behind this approach is we are checking if the i’th position is suitable candidate for a starting point or not. For checking this we are storing the capacity from front and from end.

Below is the implementation of above approach:

Please Login to comment...

• Morgan Stanley
• How to Delete Whatsapp Business Account?
• Discord vs Zoom: Select The Efficienct One for Virtual Meetings?
• Otter AI vs Dragon Speech Recognition: Which is the best AI Transcription Tool?
• Google Messages To Let You Send Multiple Photos
• 30 OOPs Interview Questions and Answers (2024)

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Our Effort to provide you the best solutions requires some appreciation

Please disable your adblocker and refresh, problem statement :, view more similar problems, median updates.

The median M of numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median. Input: The first line is an integer, N , that indicates the number o

Maximum Element

You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. Input Format The first line of input contains an integer, N . The next N lines each contain an above mentioned query. (It is guaranteed that each

Balanced Brackets

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of bra

Equal Stacks

ou have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times. Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of

Game of Two Stacks

Alexa has two stacks of non-negative integers, stack A = [a0, a1, . . . , an-1 ] and stack B = [b0, b1, . . . , b m-1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game: In each move, Nick can remove one integer from the top of either stack A or stack B. Nick keeps a running sum of the integers he removes from the two stacks. Nick is disqualified f

Largest Rectangle

Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed. There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by . If you join adjacent buildings, they will form a solid rectangle

Truck Tour or Gas Station

Categories:.

• greedy algorithm

Truck Tour (HackerRank)

Truck Tour | HackerRank

Suppose there is a circle. There are $N$ petrol pumps on that circle. Petrol pumps are numbered $0$ to $N-1$ (both inclusive).

You have two pieces of information corresponding to each of the petrol pump:

• the amount of petrol that particular petrol pump will give,
• the distance from that petrol pump to the next petrol pump.

Initially, you have a tank of infinite capacity carrying no petrol. You can start the tour at any of the petrol pumps.

Calculate the first point from where the truck will be able to complete the circle. Consider that the truck will stop at each of the petrol pumps. The truck will move one kilometer for each litre of the petrol.

Input Format

The first line will contain the value of $N$.

The next $N$ lines will contain a pair of integers each:

• the amount of petrol that petrol pump will give;
• the distance between that petrol pump and the next petrol pump.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq \text{amount of petrol},~\text{distance} \leq 10^9$

Output Format

An integer which will be the smallest index of the petrol pump from which we can start the tour.

Sample test case

Explanation.

We can start the tour from the second petrol pump.

Gas Station (LeetCode)

Gas Station - LeetCode

There are n gas stations along a circular route, where the amount of gas at the $i^{th}$ station is gas[i] .

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the $i^{th}$ 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 .

• Start at station 3 (index 3) and fill up with 4 unit of gas. Your $\text{tank} = 0 + 4 = 4$.
• Travel to station 4. Your $\text{tank} = 4 - 1 + 5 = 8$.
• Travel to station 0. Your $\text{tank} = 8 - 2 + 1 = 7$.
• Travel to station 1. Your $\text{tank} = 7 - 3 + 2 = 6$.
• Travel to station 2. Your $\text{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.
• 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 $\text{tank} = 0 + 4 = 4$.
• Travel to station 0. Your $\text{tank} = 4 - 3 + 2 = 3$.
• Travel to station 1. Your $\text{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.

Greedy algorithm .

DEV Community

Posted on Jun 14, 2021

Solution: Maximum Units on a Truck

This is part of a series of Leetcode solution explanations ( index ). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums .

Leetcode Problem #1710 ( Easy ): Maximum Units on a Truck

Description:.

( Jump to : Solution Idea || Code : JavaScript | Python | Java | C++ )

You are assigned to put some amount of boxes onto one truck . You are given a 2D array boxTypes , where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] : numberOfBoxes i is the number of boxes of type i . numberOfUnitsPerBox i is the number of units in each box of the type i . You are also given an integer truckSize , which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize . Return the maximum total number of units that can be put on the truck .

Example 1: Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4 Output: 8 Explanation: There are: - 1 box of the first type that contains 3 units. - 2 boxes of the second type that contain 2 units each. - 3 boxes of the third type that contain 1 unit each. You can take all the boxes of the first and second types, and one box of the third type. The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8. Example 2: Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 Output: 91

Constraints:

1 <= boxTypes.length <= 1000 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000 1 <= truckSize <= 10^6

( Jump to : Problem Description || Code : JavaScript | Python | Java | C++ )

For this problem, we simply need to prioritize the more valuable boxes first. To do this, we should sort the boxtypes array ( B ) in descending order by the number of units per box ( B[i][1] ).

Then we can iterate through B and at each step, we should add as many of the boxes as we can, until we reach the truck size ( T ). We should add the number of boxes added multiplied by the units per box to our answer ( ans ), and decrease T by the same number of boxes .

Once the truck is full ( T == 0 ), or once the iteration is done, we should return ans .

• Time Complexity: O(N log N) where N is the length of B , for the sort
• Space Complexity: O(1)

Javascript Code:

( Jump to : Problem Description || Solution Idea )

Python Code:

Top comments (0).

Templates let you quickly answer FAQs or store snippets for re-use.

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink .

Hide child comments as well

For further actions, you may consider blocking this person and/or reporting abuse

Sensor APIs

Sukhpinder Singh - Mar 20

⚛️ Folder Structures in React Projects

Will T. - Mar 20

JavaScript WebRTC. WebRTC example JavaScript 🌐Remote Controller

PiterDev - Mar 19

Learnt Next.JS in 1 week!! and here is GenAI Chat

Abhishek Sinha - Mar 6

We're a place where coders share, stay up-to-date and grow their careers.

Instantly share code, notes, and snippets.

samarthsewlani / Truck Tour 1.py

• Star 0 You must be signed in to star a gist
• Fork 0 You must be signed in to fork a gist
• Embed Embed this gist in your website.
• Share Copy sharable link for this gist.
• Clone via HTTPS Clone using the web URL.
• Learn more about clone URLs

• Data Structures
• Discussions

You are viewing a single comment's thread. Return to all comments →

Here's the Python solution. Poorly state assumption, don't believe I read that there will be enough fuel along the circle for all the stops.