Bird and Max Fruit Gathering

Problem Overview

Trees sit in a circle and the bird walks m steps along neighbors.

Intuition

Trees sit in a circle and the bird walks m steps along neighbors. Each visit adds that tree value again, so m steps equal floor(m/n) full laps plus a leftover arc of length m % n. Full laps contribute the circle sum that many times. The leftover is the maximum sum of any contiguous circular window of that length.

Algorithm

1Build prefix sums of the fruit array.
2Add (m / n) * totalSum as the base from complete laps.
3Let rem = m % n. If rem is 0, return the base.
4For every start i, score the next rem trees, wrapping with prefix[n] - prefix[i] + prefix[extra] when needed.
5Return base plus the best rem window.

Example Walkthrough

Input: arr = [7, 2, 1, 3, 4], m = 2

1. No full lap. Check every length-2 arc.
2. Linear arcs top out at 9. The wrap 4 + 7 = 11 is best.

Output: 11

Common Pitfalls

• Add the leftover window to the full-lap base. Taking max(base, window) drops fruits from complete circles.
• When rem = 0, do not invent an empty window; the answer is exactly the lap total.
• Wrapping arcs need the suffix from i plus a prefix of length rem - (n - i).
• If m is large, reduce with m / n and m % n instead of simulating every step.

Bird and Max Fruit Gathering.java

Java

// Approach: Trees form a circle. Visiting m trees wraps and can re-collect, so
// the total is (m / n) full circle sums plus the best contiguous arc of length
// m % n (possibly wrapping). Prefix sums answer every arc in O(1).
// Complexity: O(n) time and O(n) extra space.
import java.util.*;

class Solution {

    public int maxFruits(ArrayList<Integer> arr, int m) {
        int l = arr.size();
        int[] pref = new int[l + 1];
        for (int i = 0; i < l; i++) {
            pref[i + 1] = pref[i] + arr.get(i);
        }

        int full = m / l;
        int rem = m % l;
        int base = pref[l] * full;
        if (rem == 0) {
            return base;
        }

        int best = 0;
        for (int i = 0; i < l; i++) {
            if (i + rem >= l) {
                int extra = rem - (l - i);
                best = Math.max(best, pref[l] - pref[i] + pref[extra]);
            } else {
                best = Math.max(best, pref[i + rem] - pref[i]);
            }
        }
        return base + best;
    }
}

Was this solution helpful?