Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
You are given two integer arrays of size 2: d = [d1, d2] and r = [r1, r2].
Two delivery drones are tasked with completing a specific number of deliveries. Drone i must complete di deliveries.
Each delivery takes exactly one hour and only one drone can make a delivery at any given hour.
Additionally, both drones require recharging at specific intervals during which they cannot make deliveries. Drone i must recharge every ri hours (i.e. at hours that are multiples of ri).
Return an integer denoting the minimum total time (in hours) required to complete all deliveries.
Example 1:
Input: d = [3,1], r = [2,3]
Output: 5
Explanation:
Example 2:
Input: d = [1,3], r = [2,2]
Output: 7
Explanation:
Example 3:
Input: d = [2,1], r = [3,4]
Output: 3
Explanation:
Constraints:
d = [d1, d2]1 <= di <= 109r = [r1, r2]2 <= ri <= 3 * 104Problem summary: You are given two integer arrays of size 2: d = [d1, d2] and r = [r1, r2]. Two delivery drones are tasked with completing a specific number of deliveries. Drone i must complete di deliveries. Each delivery takes exactly one hour and only one drone can make a delivery at any given hour. Additionally, both drones require recharging at specific intervals during which they cannot make deliveries. Drone i must recharge every ri hours (i.e. at hours that are multiples of ri). Return an integer denoting the minimum total time (in hours) required to complete all deliveries.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Binary Search
[3,1] [2,3]
[1,3] [2,2]
[2,1] [3,4]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
// package main
//
// import "sort"
//
// // https://space.bilibili.com/206214
// func minimumTime1(d, r []int) int64 {
// d1, d2 := d[0], d[1]
// r1, r2 := r[0], r[1]
// l := lcm(r1, r2)
//
// // 库函数是左闭右开区间
// left := d1 + d2
// right := (d1+d2)*2 - 1
// ans := left + sort.Search(right-left, func(t int) bool {
// t += left
// return d1 <= t-t/r1 && d2 <= t-t/r2 && d1+d2 <= t-t/l
// })
// return int64(ans)
// }
//
// func f(d, r int) int {
// return (d-1)/(r-1) + 1
// }
//
// func minimumTime(d, r []int) int64 {
// d1, d2 := d[0], d[1]
// r1, r2 := r[0], r[1]
// l := lcm(r1, r2)
// return int64(max(f(d1, r1), f(d2, r2), f(d1+d2, l)))
// }
//
// func gcd(a, b int) int {
// for a != 0 {
// a, b = b%a, a
// }
// return b
// }
//
// func lcm(a, b int) int {
// return a / gcd(a, b) * b
// }
// Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
package main
import "sort"
// https://space.bilibili.com/206214
func minimumTime1(d, r []int) int64 {
d1, d2 := d[0], d[1]
r1, r2 := r[0], r[1]
l := lcm(r1, r2)
// 库函数是左闭右开区间
left := d1 + d2
right := (d1+d2)*2 - 1
ans := left + sort.Search(right-left, func(t int) bool {
t += left
return d1 <= t-t/r1 && d2 <= t-t/r2 && d1+d2 <= t-t/l
})
return int64(ans)
}
func f(d, r int) int {
return (d-1)/(r-1) + 1
}
func minimumTime(d, r []int) int64 {
d1, d2 := d[0], d[1]
r1, r2 := r[0], r[1]
l := lcm(r1, r2)
return int64(max(f(d1, r1), f(d2, r2), f(d1+d2, l)))
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
func lcm(a, b int) int {
return a / gcd(a, b) * b
}
# Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
# Time: O(logr + logd)
# Space: O(1)
# binary search, number theory
class Solution(object):
def minimumTime(self, d, r):
"""
:type d: List[int]
:type r: List[int]
:rtype: int
"""
def gcd(a, b):
while b:
a, b = b, a%b
return a
def lcm(a, b):
return a//gcd(a,b)*b
def binary_search(left, right, check):
while left <= right:
mid = left+(right-left)//2
if check(mid):
right = mid-1
else:
left = mid+1
return left
def check(t):
return t-t//r[0] >= d[0] and t-t//r[1] >= d[1] and t-t//l >= d[0]+d[1]
l = lcm(r[0], r[1])
return binary_search(sum(d), sum(d)*2, check)
// Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
// package main
//
// import "sort"
//
// // https://space.bilibili.com/206214
// func minimumTime1(d, r []int) int64 {
// d1, d2 := d[0], d[1]
// r1, r2 := r[0], r[1]
// l := lcm(r1, r2)
//
// // 库函数是左闭右开区间
// left := d1 + d2
// right := (d1+d2)*2 - 1
// ans := left + sort.Search(right-left, func(t int) bool {
// t += left
// return d1 <= t-t/r1 && d2 <= t-t/r2 && d1+d2 <= t-t/l
// })
// return int64(ans)
// }
//
// func f(d, r int) int {
// return (d-1)/(r-1) + 1
// }
//
// func minimumTime(d, r []int) int64 {
// d1, d2 := d[0], d[1]
// r1, r2 := r[0], r[1]
// l := lcm(r1, r2)
// return int64(max(f(d1, r1), f(d2, r2), f(d1+d2, l)))
// }
//
// func gcd(a, b int) int {
// for a != 0 {
// a, b = b%a, a
// }
// return b
// }
//
// func lcm(a, b int) int {
// return a / gcd(a, b) * b
// }
// Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3733: Minimum Time to Complete All Deliveries
// package main
//
// import "sort"
//
// // https://space.bilibili.com/206214
// func minimumTime1(d, r []int) int64 {
// d1, d2 := d[0], d[1]
// r1, r2 := r[0], r[1]
// l := lcm(r1, r2)
//
// // 库函数是左闭右开区间
// left := d1 + d2
// right := (d1+d2)*2 - 1
// ans := left + sort.Search(right-left, func(t int) bool {
// t += left
// return d1 <= t-t/r1 && d2 <= t-t/r2 && d1+d2 <= t-t/l
// })
// return int64(ans)
// }
//
// func f(d, r int) int {
// return (d-1)/(r-1) + 1
// }
//
// func minimumTime(d, r []int) int64 {
// d1, d2 := d[0], d[1]
// r1, r2 := r[0], r[1]
// l := lcm(r1, r2)
// return int64(max(f(d1, r1), f(d2, r2), f(d1+d2, l)))
// }
//
// func gcd(a, b int) int {
// for a != 0 {
// a, b = b%a, a
// }
// return b
// }
//
// func lcm(a, b int) int {
// return a / gcd(a, b) * b
// }
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.