Given that there is an infinite number of points 1, 2, 3… on the X axis and your current position is cur. There are N taxis near you, and the position of those taxis is given as an array pos[]. Where pos[i] denotes the position of the ith taxi. You are also given an array of time[], where time[i] denotes the time taken by the ith taxi to cover 1 unit of distance. Your task is to find the minimum time to board a taxi.
Examples:
Input: N = 3, cur = 4, pos = [1, 5, 6], time = [2, 3, 1]
Output: 2
Explanation:
- Total time taken by the 1st taxi will be: (4-1)*2 = 6
- Total time taken by the 2nd taxi will be: (5-4)*3 = 3
- Total time taken by the 3rd taxi will be: (6-4)*1 = 2
So, the minimum time will be 2 sec.
Input:N = 2, cur = 1, pos = [1, 6], time = [10, 3]
Output: 0
Explanation:
- Total time taken by the 1st taxi will be: (1-1)*10 = 0
- Total time taken by the 2nd taxi will be: (6-1)*3 = 15
So, the minimum time will be 0 sec.
Approach: This can be solved with the following idea:
Iterate over the array and count the minimum time for each.
Below are the steps involved in the implementation of the code:
- Initialize minn as the maximum integer possible
- Iterate over the array.
- Find the distance between the passenger and each taxi position.
- Find the minimum distance by multiplying it by the time[i] required.
- Update the minn.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find minimum time required int minimumTime( int N, int cur, vector< int >& pos, vector< int >& time ) { int minn = INT_MAX; int i = 0; // Iterate over the array while (i < N) { minn = min(minn, abs (pos[i] - cur) * time [i]); i++; } return minn; } // Driver code int main() { int N = 3; int 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
// JAVA code for the above approach: import java.util.*; public class GFG { // Function to find minimum time required public static int minimumTime( int N, int cur, List<Integer> pos, List<Integer> time) { int minn = Integer.MAX_VALUE; int i = 0 ; // Iterate over the array while (i < N) { minn = Math.min(minn, Math.abs(pos.get(i) - cur) * time.get(i)); i++; } return minn; } // Driver code public static void main(String[] args) { int N = 3 ; int cur = 4 ; List<Integer> pos = new ArrayList<>(Arrays.asList( 1 , 5 , 6 )); List<Integer> time = new ArrayList<>(Arrays.asList( 2 , 3 , 1 )); // Function call System.out.println(minimumTime(N, cur, pos, time)); } } // This code is contributed by rambabuguphka |
Python3
# Python3 code for the above approach: # Function to find minimum time required def minimumTime(N, cur, pos, time): minn = float ( 'inf' ) i = 0 # Iterate over the array while i < N: minn = min (minn, abs (pos[i] - cur) * time[i]) i + = 1 return minn # 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 rambabuguphka |
C#
// C# code for the above approach: using System; using System.Collections.Generic; class GFG { // Function to find minimum time required static int MinimumTime( int N, int cur, List< int > pos, List< int > time) { int minn = int .MaxValue; int i = 0; // Iterate over the list while (i < N) { minn = Math.Min(minn, Math.Abs(pos[i] - cur) * time[i]); i++; } return minn; } static void Main( string [] args) { int N = 3; int 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 shivamgupta310570 |
Javascript
// Function to find minimum time required function minimumTime(N, cur, pos, time) { let minn = Infinity; let i = 0; // Iterate over the array while (i < N) { minn = Math.min(minn, Math.abs(pos[i] - cur) * time[i]); i++; } return minn; } // Driver 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 shivamgupta0987654321 |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!