Minimum time to reach given points on X-axis
Given an array pos[] that represents N points on the X axis, a variable cur that represents the current position, and an array time. Where time[i] denotes the time taken to cover 1 unit of distance toward ith point, the task is to reach at any of the given points in minimum time and print the minimum time taken.
Examples:
Input: N = 3, cur = 4, pos = {1, 5, 6}, time = {2, 3, 1}
Output: 2
Explanation: We will go position 6 which will take 1 unit time to cover 1 unit distance and the distance between current position and 6 is 2 so answer will be 2.Input: N = 2, cur = 1, pos = {1, 6}, time = {10, 3}
Output: 0
Explanation: We are already at point 1.
Approach: To solve the problem follow the below idea:
- Calculate the distance between each point by distance = abs(cur-pos[i]) where pos[i] is ith point. So after finding it calculate the time to reach at that point distance*time[i].
- Traverse all the point and find out the distance between the point and current position.
- Multiply the distance with time to cover 1 unit toward that point.
- Find the smallest from all.
Follow the steps to solve the problem:
- Initialize a variable say ans = INT_MAX to store the minimum time required to reach any of the given points.
- Iterate the points[] array and for each point, calculate the distance between the current position and the point, distance = abs(cur – pos[i]).
- Multiply the distance with the corresponding time required to reach that point from the time array.
- Update the ans variable with the minimum of its current value and the calculated value.
- Return ans.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find minimum time int minimumTime( int N, int cur, vector< int >& pos, vector< int >& time ) { // Taking our answer as maximum int ans = INT_MAX; // Iterating over array for ( int i = 0; i < N; i++) { // Finding distance between // current position ans point int distance = abs (cur - pos[i]); // taking minimum ans = min(ans, distance * time [i]); } return ans; } // Drivers code int main() { int N = 3, cur = 4; vector< int > pos = { 1, 5, 6 }; vector< int > time = { 2, 3, 1 }; // Function Call cout << minimumTime(N, cur, pos, time ); return 0; } |
Java
import java.util.*; public class GFG { // Function to find minimum time static int minimumTime( int N, int cur, ArrayList<Integer> pos, ArrayList<Integer> time) { // Taking our answer as maximum int ans = Integer.MAX_VALUE; // Iterating over array for ( int i = 0 ; i < N; i++) { // Finding distance between // current position and point int distance = Math.abs(cur - pos.get(i)); // taking minimum ans = Math.min(ans, distance * time.get(i)); } return ans; } // Drivers code public static void main(String[] args) { int N = 3 , cur = 4 ; ArrayList<Integer> pos = new ArrayList<Integer>(); pos.add( 1 ); pos.add( 5 ); pos.add( 6 ); ArrayList<Integer> time = new ArrayList<Integer>(); time.add( 2 ); time.add( 3 ); time.add( 1 ); // Function Call System.out.println(minimumTime(N, cur, pos, time)); } } //contributed by tushar rokade |
Python3
# Function to find minimum time def minimumTime(N, cur, pos, time): # Taking our answer as maximum ans = float ( 'inf' ) # Iterating over array for i in range (N): # Finding distance between # current position and point distance = abs (cur - pos[i]) # taking minimum ans = min (ans, distance * time[i]) return ans # Driver code if __name__ = = '__main__' : N = 3 cur = 4 pos = [ 1 , 5 , 6 ] time = [ 2 , 3 , 1 ] # Function call print (minimumTime(N, cur, pos, time)) #This code is contributed by Adi |
C#
// C# code for the above approach: using System; using System.Collections.Generic; public class GFG { // Function to find minimum time static int MinimumTime( int N, int cur, List< int > pos, List< int > time) { // Taking our answer as maximum int ans = int .MaxValue; // Iterating over list for ( int i = 0; i < N; i++) { // Finding distance between // current position and point int distance = Math.Abs(cur - pos[i]); // taking minimum ans = Math.Min(ans, distance * time[i]); } return ans; } // Driver code public static void Main( string [] args) { int N = 3, cur = 4; List< int > pos = new List< int > { 1, 5, 6 }; List< int > time = new List< int > { 2, 3, 1 }; // Function Call Console.WriteLine(MinimumTime(N, cur, pos, time)); } } // This code is contributed by Utkarsh Kumar |
Javascript
// Javascript code for the above approach: // Function to find minimum time function minimumTime(N, cur, pos, time) { // Taking our answer as maximum let ans = Infinity; // Iterating over array for (let i = 0; i < N; i++) { // Finding distance between // current position ans point let distance = Math.abs(cur - pos[i]); // taking minimum ans = Math.min(ans, distance * time[i]); } return ans; } // Drivers code const N = 3; const cur = 4; const pos = [1, 5, 6]; const time = [2, 3, 1]; // Function Call console.log(minimumTime(N, cur, pos, time)); // This code is contributed by Pushpesh Raj. |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us