Minimize Acceleration of Car to Cover Track
Given an array times[] of size n and a positive integer trackLength, where each element in times[] represent exact time where the car’s acceleration will be increased to k meters per second and then decreased by 1 meter per second until it reaches 0. The task is to minimize the acceleration of car (i.e, k) to cover the trackLength.
Examples:
Input: trackLength: 20, n = 3, times[] = {1, 5, 9}
Output: 4
Explanation: Cast a time at times[0] = 1, car’s speed reaches k = 4 m/s. During the 1st second, the car moves 4 meters, 3 meters in the 2nd second, 2 meters in the 3rd second, 1 meter in the 4th second, 4 meters in the 5th second, 3 meter in the 6th second, 2 meter in the 7th second, 1 meter in the 8th second. Hence, trackLength completed at 8th second.Input: trackLength = 10, n = 3, times[] = {3, 4, 5}
Output: 3
Approach: This can be solved with the following idea:
Using Binary Search on Answer technique, we can easily calculate if we take a speed k are we able to complete the track length. By seeing the difference between times and check how much distance are we able to cover up.
Step-by-step approach:
- Initialize l = 1 and r = trackLength.
- Using Binary Search, we can find out the minimum value of k
- Calculate mid = l + (r – l) / 2
- For this mid, check whether are we able to complete tracklength by using all the time:
- Start from first timing, cast it until next time comes. As, it is always optimal to get the speed again at each time we are given.
- Check the difference between time given, According to that increase in distance.
- If mid is valid, update the ans with mid and reduce r to mid – 1
- Otherwise increase the l to mid + 1
Below is the implementation of the above approach:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to check whether speed will be able to complete // the Track bool solve( long long speed, vector< int >& times, long long len, int n) { long long dist = 0; for ( int i = 0; i < n; i++) { if (dist >= len) { return true ; } // Calculate how much distance we can travel // before casting in another second. if (i + 1 < n) { long long diff = times[i + 1] - times[i]; if (diff >= speed) { dist += (speed * 1LL * (speed + 1)) / 2; } else { dist += (diff * 1LL * (speed + speed - diff + 1)) / 2; } } // Add distance upto speed becomes 0 else { dist += (speed * 1LL * (speed + 1)) / 2; } } // If we are able to complete trackLength if (dist >= len) { return true ; } else { return false ; } } // Function to find minimum value of k int minimizeTopSpeed( int n, vector< int >& times, long long tLength) { long long l = 1; long long r = tLength; long long ans = r; // Binary search while (l <= r) { // Calculate mid long long mid = l + (r - l) / 2; // Check if mid can be value of k if (solve(mid, times, tLength, n)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // Return the value of k return ( int )ans; } // Driver code int main() { int n = 3; int trackLength = 20; vector< int > times = { 1, 3, 5 }; // Function call cout << minimizeTopSpeed(n, times, trackLength); return 0; } |
Java
/*code by flutterfly */ import java.util.*; class Main { // Function to check whether speed will be able to complete // the Track static boolean solve( long speed, List<Integer> times, long len, int n) { long dist = 0 ; for ( int i = 0 ; i < n; i++) { if (dist >= len) { return true ; } // Calculate how much distance we can travel // before casting in another second. if (i + 1 < n) { long diff = times.get(i + 1 ) - times.get(i); if (diff >= speed) { dist += (speed * 1L * (speed + 1 )) / 2 ; } else { dist += (diff * 1L * (speed + speed - diff + 1 )) / 2 ; } } else { // Add distance up to speed becomes 0 dist += (speed * 1L * (speed + 1 )) / 2 ; } } // If we are able to complete trackLength return dist >= len; } // Function to find the minimum value of k static int minimizeTopSpeed( int n, List<Integer> times, long tLength) { long l = 1 ; long r = tLength; long ans = r; // Binary search while (l <= r) { // Calculate mid long mid = l + (r - l) / 2 ; // Check if mid can be the value of k if (solve(mid, times, tLength, n)) { ans = mid; r = mid - 1 ; } else { l = mid + 1 ; } } // Return the value of k return ( int ) ans; } // Driver code public static void main(String[] args) { int n = 3 ; int trackLength = 20 ; List<Integer> times = Arrays.asList( 1 , 3 , 5 ); // Function call System.out.println(minimizeTopSpeed(n, times, trackLength)); } } |
Python3
# code by flutterfly def solve(speed, times, length, n): dist = 0 for i in range (n): if dist > = length: return True # Calculate how much distance we can travel # before casting in another second. if i + 1 < n: diff = times[i + 1 ] - times[i] if diff > = speed: dist + = (speed * (speed + 1 )) / / 2 else : dist + = (diff * (speed + speed - diff + 1 )) / / 2 else : # Add distance up to speed becomes 0 dist + = (speed * (speed + 1 )) / / 2 # If we are able to complete track length return dist > = length def minimize_top_speed(n, times, track_length): l = 1 r = track_length ans = r # Binary search while l < = r: # Calculate mid mid = l + (r - l) / / 2 # Check if mid can be the value of k if solve(mid, times, track_length, n): ans = mid r = mid - 1 else : l = mid + 1 # Return the value of k return ans # Driver code if __name__ = = "__main__" : n = 3 track_length = 20 times = [ 1 , 3 , 5 ] # Function call print (minimize_top_speed(n, times, track_length)) |
C#
//code by flutterfly using System; using System.Collections.Generic; class MainClass { // Function to check whether speed will be able to complete // the Track static bool Solve( long speed, List< int > times, long len, int n) { long dist = 0; for ( int i = 0; i < n; i++) { if (dist >= len) { return true ; } // Calculate how much distance we can travel // before casting in another second. if (i + 1 < n) { long diff = times[i + 1] - times[i]; if (diff >= speed) { dist += (speed * (speed + 1)) / 2; } else { dist += (diff * (speed + speed - diff + 1)) / 2; } } else { // Add distance up to speed becomes 0 dist += (speed * (speed + 1)) / 2; } } // If we are able to complete track length return dist >= len; } // Function to find the minimum value of k static int MinimizeTopSpeed( int n, List< int > times, long tLength) { long l = 1; long r = tLength; long ans = r; // Binary search while (l <= r) { // Calculate mid long mid = l + (r - l) / 2; // Check if mid can be the value of k if (Solve(mid, times, tLength, n)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // Return the value of k return ( int )ans; } // Driver code public static void Main( string [] args) { int n = 3; int trackLength = 20; List< int > times = new List< int > { 1, 3, 5 }; // Function call Console.WriteLine(MinimizeTopSpeed(n, times, trackLength)); } } |
Javascript
//code by flutterfly // Function to check whether speed will be able to complete // the Track function solve(speed, times, len, n) { let dist = 0; for (let i = 0; i < n; i++) { if (dist >= len) { return true ; } // Calculate how much distance we can travel // before casting in another second. if (i + 1 < n) { let diff = times[i + 1] - times[i]; if (diff >= speed) { dist += (speed * (speed + 1)) / 2; } else { dist += (diff * (speed + speed - diff + 1)) / 2; } } else { // Add distance up to speed becomes 0 dist += (speed * (speed + 1)) / 2; } } // If we are able to complete track length return dist >= len; } // Function to find the minimum value of k function minimizeTopSpeed(n, times, tLength) { let l = 1; let r = tLength; let ans = r; // Binary search while (l <= r) { // Calculate mid let mid = l + Math.floor((r - l) / 2); // Check if mid can be the value of k if (solve(mid, times, tLength, n)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // Return the value of k return ans; } // Driver code let n = 3; let trackLength = 20; let times = [1, 3, 5]; // Function call console.log(minimizeTopSpeed(n, times, trackLength)); |
4
Time Complexity: O(N log N)
Auxiliary Space: O(1)
Contact Us