Minimum Number of Days to Eat N Oranges
Problem
You have n oranges. Each day you may do exactly one of the following: eat one orange; if the current count is divisible by 2, eat n/2 oranges (halving the count); or if the current count is divisible by 3, eat 2·(n/3) oranges (leaving n/3). Return the minimum number of days needed to eat all n oranges.
n = 104from collections import deque
def min_days(n):
seen = {n}
q = deque([n])
days = 0
while q:
for _ in range(len(q)):
x = q.popleft()
if x == 0:
return days
nxts = [x - 1]
if x % 2 == 0:
nxts.append(x // 2)
if x % 3 == 0:
nxts.append(x // 3)
for y in nxts:
if y not in seen:
seen.add(y)
q.append(y)
days += 1
return daysfunction minDays(n) {
const seen = new Set([n]);
let q = [n];
let days = 0;
while (q.length) {
const next = [];
for (const x of q) {
if (x === 0) return days;
const nxts = [x - 1];
if (x % 2 === 0) nxts.push(x / 2);
if (x % 3 === 0) nxts.push(x / 3);
for (const y of nxts) {
if (!seen.has(y)) {
seen.add(y);
next.push(y);
}
}
}
q = next;
days++;
}
return days;
}class Solution {
public int minDays(int n) {
Set<Integer> seen = new HashSet<>();
Deque<Integer> q = new ArrayDeque<>();
seen.add(n); q.add(n);
int days = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int x = q.poll();
if (x == 0) return days;
List<Integer> nxts = new ArrayList<>();
nxts.add(x - 1);
if (x % 2 == 0) nxts.add(x / 2);
if (x % 3 == 0) nxts.add(x / 3);
for (int y : nxts) {
if (!seen.contains(y)) {
seen.add(y); q.add(y);
}
}
}
days++;
}
return days;
}
}class Solution {
public:
int minDays(int n) {
unordered_set<int> seen{n};
queue<int> q;
q.push(n);
int days = 0;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int x = q.front(); q.pop();
if (x == 0) return days;
vector<int> nxts{x - 1};
if (x % 2 == 0) nxts.push_back(x / 2);
if (x % 3 == 0) nxts.push_back(x / 3);
for (int y : nxts) {
if (!seen.count(y)) {
seen.insert(y); q.push(y);
}
}
}
days++;
}
return days;
}
};Explanation
Think of each possible remaining count as a node. From a count x you can move to x-1 (eat one), to x/2 when x is divisible by 2, and to x/3 when divisible by 3. Every such move costs exactly one day, so the minimum days is the shortest path from n down to 0 in this graph.
With unit-cost edges, breadth-first search from n finds that shortest path. We expand the graph one day-layer at a time: all counts reachable in 0 days, then 1 day, then 2, and so on. The first layer that contains 0 tells us the answer.
A seen set keeps us from revisiting a count. This is what makes it efficient — the powerful divide moves shrink the number so quickly that only a small set of distinct counts is ever reachable, even for huge n. The naive "eat one at a time" path of length n is pruned away because the halving and thirding moves reach 0 in far fewer layers.
The same recurrence can be written with memoization as days(x) = 1 + min(x%2 + days(x/2), x%3 + days(x/3)): spend a few single-orange days to make x divisible, then take the big divide. The BFS shown here computes the identical answer breadth-first.
Worked example, n = 10: layer 0 = {10}. From 10 we reach 9 (eat 1) and 5 (÷2). From 9 we reach 3 (÷3); from 5 we reach 4. Continuing, 3 reaches 1 (÷3), then 1 reaches 0. The first time 0 appears is at layer 4, so the answer is 4.