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 jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:
Example 1:
Input: x = 3, y = 5, target = 4
Output: true
Explanation:
Follow these steps to reach a total of 4 liters:
Reference: The Die Hard example.
Example 2:
Input: x = 2, y = 6, target = 5
Output: false
Example 3:
Input: x = 1, y = 2, target = 3
Output: true
Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.
Constraints:
1 <= x, y, target <= 103Problem summary: You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations: Fill either jug completely with water. Completely empty either jug. Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
3 5 4
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #365: Water and Jug Problem
class Solution {
private Set<Long> vis = new HashSet<>();
private int x, y, z;
public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
x = jug1Capacity;
y = jug2Capacity;
z = targetCapacity;
return dfs(0, 0);
}
private boolean dfs(int i, int j) {
long st = f(i, j);
if (!vis.add(st)) {
return false;
}
if (i == z || j == z || i + j == z) {
return true;
}
if (dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0)) {
return true;
}
int a = Math.min(i, y - j);
int b = Math.min(j, x - i);
return dfs(i - a, j + a) || dfs(i + b, j - b);
}
private long f(int i, int j) {
return i * 1000000L + j;
}
}
// Accepted solution for LeetCode #365: Water and Jug Problem
func canMeasureWater(x int, y int, z int) bool {
type pair struct{ x, y int }
vis := map[pair]bool{}
var dfs func(int, int) bool
dfs = func(i, j int) bool {
st := pair{i, j}
if vis[st] {
return false
}
vis[st] = true
if i == z || j == z || i+j == z {
return true
}
if dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0) {
return true
}
a := min(i, y-j)
b := min(j, x-i)
return dfs(i-a, j+a) || dfs(i+b, j-b)
}
return dfs(0, 0)
}
# Accepted solution for LeetCode #365: Water and Jug Problem
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
def dfs(i: int, j: int) -> bool:
if (i, j) in vis:
return False
vis.add((i, j))
if i == z or j == z or i + j == z:
return True
if dfs(x, j) or dfs(i, y) or dfs(0, j) or dfs(i, 0):
return True
a = min(i, y - j)
b = min(j, x - i)
return dfs(i - a, j + a) or dfs(i + b, j - b)
vis = set()
return dfs(0, 0)
// Accepted solution for LeetCode #365: Water and Jug Problem
struct Solution;
use std::collections::VecDeque;
impl Solution {
fn can_measure_water(x: i32, y: i32, z: i32) -> bool {
if z > x + y {
return false;
}
if z == x || z == y || z == x + y {
return true;
}
let mut visited = vec![false; (x + y) as usize];
let mut queue: VecDeque<i32> = VecDeque::new();
queue.push_back(0);
while let Some(front) = queue.pop_front() {
for diff in [x, y, -x, -y].iter() {
let next = front + diff;
if next == z {
return true;
} else {
if next < x + y && next > 0 && !visited[next as usize] {
visited[next as usize] = true;
queue.push_back(next);
}
}
}
}
false
}
}
#[test]
fn test() {
let x = 3;
let y = 5;
let z = 4;
let res = true;
assert_eq!(Solution::can_measure_water(x, y, z), res);
let x = 2;
let y = 6;
let z = 5;
let res = false;
assert_eq!(Solution::can_measure_water(x, y, z), res);
}
// Accepted solution for LeetCode #365: Water and Jug Problem
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #365: Water and Jug Problem
// class Solution {
// private Set<Long> vis = new HashSet<>();
// private int x, y, z;
//
// public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
// x = jug1Capacity;
// y = jug2Capacity;
// z = targetCapacity;
// return dfs(0, 0);
// }
//
// private boolean dfs(int i, int j) {
// long st = f(i, j);
// if (!vis.add(st)) {
// return false;
// }
// if (i == z || j == z || i + j == z) {
// return true;
// }
// if (dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0)) {
// return true;
// }
// int a = Math.min(i, y - j);
// int b = Math.min(j, x - i);
// return dfs(i - a, j + a) || dfs(i + b, j - b);
// }
//
// private long f(int i, int j) {
// return i * 1000000L + j;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
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.