Challenge lab in ADT Contracts and Complexity

Mission

For a power-of-two n, report the number of halving levels and the total n log2(n) combine work.

Learning outcome: Defend a divide-and-conquer complexity estimate

Correctness contract

Invariant: An ADT contract describes observable behavior independently from implementation.

Required technique: Derive log2(n) by repeated halving and multiply the level count by n.

Complexity target: time O(log n); space O(1).

Input and output

Input: One positive power-of-two integer n. Whitespace may be spaces or line breaks.

Output: Print levels=<log2(n)> work=<n*log2(n)>. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is a positive power of two and fits in a signed 64-bit integer.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Derive log2(n) by repeated halving and multiply the level count by n.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

8

Sample output

levels=3 work=24

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Repeated halving gives log2(n) levels, and each level contributes n units of combine work. Input `8` therefore produces `levels=3 work=24`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.