365. Water and Jug Problem
Tags:
Medium
Skills:
Math
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài hỏi có thể đo được chính xác lượng nước target bằng hai bình có dung tích jug1 và jug2 thông qua các thao tác đổ đầy, làm trống hoặc chuyển nước giữa hai bình
Approach - GCD
Nguyên lý cơ bản
Các bước kiểm tra
Time and space complexity
Solution
1function canMeasureWater(x: number, y: number, target: number): boolean {
2 if (x + y < target) {
3 return false;
4 }
5 if (x === 0 || y === 0) {
6 return target === 0 || x + y === target
7 }
8 return target % gcd(x, y) === 0
9};
10
11function gcd(a: number, b: number): number {
12 while (b !== 0) {
13 const temp = b;
14 b = a % b;
15 a = temp;
16 }
17 return a;
18}
19