|
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++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
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;
}
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;
}
}
else {
dist += (speed * 1LL * (speed + 1)) / 2;
}
}
if (dist >= len) {
return true;
}
else {
return false;
}
}
int minimizeTopSpeed(int n, vector<int>& times,
long long tLength)
{
long long l = 1;
long long r = tLength;
long long ans = r;
while (l <= r) {
long long mid = l + (r - l) / 2;
if (solve(mid, times, tLength, n)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return (int)ans;
}
int main()
{
int n = 3;
int trackLength = 20;
vector<int> times = { 1, 3, 5 };
cout << minimizeTopSpeed(n, times, trackLength);
return 0;
}
|
Java
import java.util.*;
class Main {
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;
}
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 {
dist += (speed * 1L * (speed + 1)) / 2;
}
}
return dist >= len;
}
static int minimizeTopSpeed(int n, List<Integer> times,
long tLength) {
long l = 1;
long r = tLength;
long ans = r;
while (l <= r) {
long mid = l + (r - l) / 2;
if (solve(mid, times, tLength, n)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return (int) ans;
}
public static void main(String[] args) {
int n = 3;
int trackLength = 20;
List<Integer> times = Arrays.asList(1, 3, 5);
System.out.println(minimizeTopSpeed(n, times, trackLength));
}
}
|
Python3
def solve(speed, times, length, n):
dist = 0
for i in range(n):
if dist >= length:
return True
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:
dist += (speed * (speed + 1)) // 2
return dist >= length
def minimize_top_speed(n, times, track_length):
l = 1
r = track_length
ans = r
while l <= r:
mid = l + (r - l) // 2
if solve(mid, times, track_length, n):
ans = mid
r = mid - 1
else:
l = mid + 1
return ans
if __name__ == "__main__":
n = 3
track_length = 20
times = [1, 3, 5]
print(minimize_top_speed(n, times, track_length))
|
C#
using System;
using System.Collections.Generic;
class MainClass
{
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;
}
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
{
dist += (speed * (speed + 1)) / 2;
}
}
return dist >= len;
}
static int MinimizeTopSpeed(int n, List<int> times, long tLength)
{
long l = 1;
long r = tLength;
long ans = r;
while (l <= r)
{
long mid = l + (r - l) / 2;
if (Solve(mid, times, tLength, n))
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return (int)ans;
}
public static void Main(string[] args)
{
int n = 3;
int trackLength = 20;
List<int> times = new List<int> { 1, 3, 5 };
Console.WriteLine(MinimizeTopSpeed(n, times, trackLength));
}
}
|
Javascript
function solve(speed, times, len, n) {
let dist = 0;
for (let i = 0; i < n; i++) {
if (dist >= len) {
return true;
}
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 {
dist += (speed * (speed + 1)) / 2;
}
}
return dist >= len;
}
function minimizeTopSpeed(n, times, tLength) {
let l = 1;
let r = tLength;
let ans = r;
while (l <= r) {
let mid = l + Math.floor((r - l) / 2);
if (solve(mid, times, tLength, n)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
let n = 3;
let trackLength = 20;
let times = [1, 3, 5];
console.log(minimizeTopSpeed(n, times, trackLength));
|
Time Complexity: O(N log N)
Auxiliary Space: O(1)
|
