# Indexing and boundary arithmetic workbook

40 exercises on fenceposts, off-by-one errors, zero-based and one-based indexing, and the arithmetic needed to avoid them.

Work through the exercises before opening the solutions. Exercises 1–10 establish the arithmetic; 11–20 apply it to everyday code; 21–30 combine several boundaries; 31–40 require invariants, derivations, or careful machine-integer reasoning. All solutions are collected after Exercise 40.

## Conventions

- `n` is a number of elements, never an index unless explicitly stated. It may be zero.
- A zero-based sequence has element indices `0` through `n-1`. A one-based sequence has element indices `1` through `n`. An empty sequence has no element indices.
- `[a,b)` means integers `i` satisfying `a <= i < b`; `[a,b]` includes both endpoints. Do not assume a programming language's slice syntax uses either convention.
- A boundary is a position between elements, including before the first and after the last. There are `n+1` boundaries. We usually label boundaries by the number of preceding elements: `0` through `n`, even for one-based sequences.
- C-like snippets use `size_t` for nonnegative sizes where shown. It is unsigned: subtracting one from zero wraps to its maximum value. Accessing outside an actual C array is not allowed. Snippets are algorithm fragments, not complete translation units.
- Lua-like snippets use dense sequences with an explicit length `n`. There are no holes. Do not infer a reliable sequence length from an arbitrary sparse table. Numeric `for` loops include the ending value when the step reaches it. Assume integer arithmetic stays representable unless an exercise says otherwise.
- Mathematical formulas use exact integers. Machine code needs additional representability and allocation checks. A logical boundary does not automatically authorize constructing a pointer to it.
- `floor(x)` rounds down and `ceil(x)` rounds up. For nonnegative integers, C integer division gives the floor. Lua integer division is written `//`.

For each coding exercise, write down the legal input domain, the meaning of each variable, and the indices actually accessed. Test empty, singleton, smallest valid, exact-fit, and just-too-large cases when relevant. “Change `<` to `<=`” is not a complete explanation: explain which set of indices is required.

## Part I — Elements, gaps, and intervals

### Exercise 1 — First and last

For lengths `0, 1, 2, 7`, give the valid element indices in both bases, the number of boundaries, and the label of the final boundary when boundaries count preceding elements. For a nonempty sequence, express the last element index in terms of `n` in each base. Explain why plugging zero into those expressions does not produce an element.

### Exercise 2 — Counting intervals

List the indices and counts in `[3,8)`, `[3,8]`, `(3,8]`, and `(3,8)`. Derive formulas for the number of integers in each kind of interval when `a <= b`, including `a=b`. Which representation naturally describes an empty interval without reversing the endpoints?

### Exercise 3 — Fences and links

A straight path has 12 posts, with one segment between consecutive posts. A closed circular fence has 12 posts. How many segments does each have? Generalize the straight case to `n >= 0`. For the circular case assume `n >= 3`. A file has `n` records: how many adjacent record pairs can be compared without wrapping?

### Exercise 4 — Translating coordinates

A sequence of length 12 is stored first in a zero-based array and then in a one-based table. Translate element index 7, interval `[3,8)`, and insertion boundary 12 into the other representation. Express the translated interval both as one-based inclusive element indices and as one-based half-open coordinates. Does every coordinate need `+1`? Distinguish a boundary's label from “the index of the next element.”

### Exercise 5 — Start plus count

A selection starts at element index `s` and contains `k` elements. Derive the last included index and exclusive endpoint in either base. Which expression has no element meaning when `k=0`? For a zero-based sequence of length `n`, allow empty selections at the final boundary and derive a validity test that avoids calculating `s+k` before checking it.

### Exercise 6 — Intersection

Compute the intersection and its length for these pairs of half-open intervals:

1. `[2,7)` and `[5,9)`.
2. `[2,5)` and `[5,9)`.
3. `[7,9)` and `[2,4)`.
4. `[4,4)` and `[1,8)`.

Give a general formula. If the intervals do not overlap, specify how your API represents the empty result without accidentally reporting a negative length.

### Exercise 7 — Splitting at a boundary

Split a length-`n` sequence at boundary `p`, where `p` elements belong on the left. Give both pieces and their lengths in zero-based half-open notation and one-based inclusive notation. State the domain of `p`. Work out `n=5` with `p=0,2,5`. What happens when `n=0`?

### Exercise 8 — The kth element from the end

Let `k=1` mean the last element. Derive the index of the kth element from the end in both bases and the validity condition. For `n=8`, calculate `k=1,3,8`. Explain the mistake in using `n-k-1` in zero-based code.

### Exercise 9 — Offsets within a subrange

A zero-based array selection is `[lo,hi)`. Its local coordinates begin at zero. Translate local index `j` to an array index and back. Repeat when the underlying sequence is one-based and the selection is inclusive `[L,R]`, with local coordinates beginning at one. Finally translate a zero-based local offset `j` into that same one-based selection. State each domain.

### Exercise 10 — Read the loop literally

For each loop, list the values for `n=0,1,4`, count its iterations, and decide whether it visits every element exactly once. Use signed mathematical integers in A–C so underflow is not yet a distraction.

```c
// A
for (int i = 0; i <= n; ++i) visit(i);
// B
for (int i = 1; i < n; ++i) visit(i);
// C
for (int i = 0; i < n; ++i) visit(i);
```

```lua
-- D
for i = 1, n do visit(i) end
-- E
for i = 0, n do visit(i) end
```

## Part II — Everyday loops and storage

### Exercise 11 — Repair adjacent comparisons

The intent is to compare each element with its successor, without wrapping.

```c
for (size_t i = 0; i <= n - 1; ++i)
    compare(a[i], a[i + 1]);
```

Find both the endpoint and empty-input bugs. Give a version whose loop condition does not evaluate `n-1` when `n=0`. Translate it into one-based Lua-like code.

### Exercise 12 — Reverse traversal

Repair this unsigned loop for all lengths:

```c
for (size_t i = n - 1; i >= 0; --i)
    use(a[i]);
```

Write a version that never decrements zero, even in the final failed condition. Give the Lua-like equivalent. Explain why “`i` is never negative” is not sufficient to show an index is valid.

### Exercise 13 — Reverse in place

Derive the partner index of element `i` in both bases. Write an in-place reversal with no redundant swaps and no self-swap of the middle element. How many swaps occur? Trace lengths `0,1,2,5,6`.

### Exercise 14 — Insertion and deletion

An array has `n` initialized elements and capacity `C`. Insert a new element at boundary `p`, shifting the suffix. State every precondition and the direction of movement. Then delete zero-based element `d`, shifting the suffix back. Write both loops and give their one-based equivalents: insertion before index `q`, including append at `q=n+1`, and deletion at index `r`. Test insertion into an empty array and deletion of the sole element.

### Exercise 15 — Strings and terminators

A C destination buffer has capacity `C` bytes. You want to copy `k` payload bytes and append a zero byte. Derive the required capacity and legal terminator index. Write an overflow-safe capacity check. Give outcomes for `(C,k)=(0,0),(1,0),(4,3),(4,4)`. Does an empty string require zero bytes of storage?

### Exercise 16 — Every sth element

Visit indices `a, a+s, a+2s, ...` strictly below `b`, with `0 <= a <= b` and `s > 0`. Derive the count and last visited index, treating the empty case separately. Evaluate `(a,b,s)=(2,14,4),(2,15,4),(5,5,3)`. Give a count formula that avoids the overflowing numerator in the common ceiling-division expression.

### Exercise 17 — Pages and chunks

Partition `n` records into chunks of capacity `c > 0`. Derive the number of nonempty chunks, the start and length of chunk `j`, and its one-based inclusive endpoints. Use zero-based chunk numbers. Work out `n=10,c=4`, `n=8,c=4`, and `n=0,c=4`. Explain why `n/c+1` is wrong.

### Exercise 18 — Sliding windows

A window contains `w > 0` consecutive elements and must fit entirely in a sequence of length `n`. Derive the number of windows and legal start positions in both bases. List the windows for `n=5,w=3`; handle `w=n` and `w>n`. If you additionally allow `w=0`, propose a coherent definition and count.

### Exercise 19 — Prefix sums

For zero-based data, define `P[t]` to be the sum of the first `t` elements. Derive initialization, construction, total storage, and the sum of `[l,r)`. For one-based data, first use a prefix table keyed `0..n`, then redesign it to use only keys `1..n+1`. Derive the sum of inclusive `[L,R]` in both designs. Include an empty-range convention.

### Exercise 20 — Overlapping copies

In a zero-based buffer, copy `k` elements from start `s` to start `d`. The two ranges may overlap. The copy must behave as if the source values were saved first. Validate both ranges without overflowing. Derive when forward movement is safe and when backward movement is necessary. Trace copying `[0,4)` to `[1,5)` in `[A,B,C,D,E]`. Write the loops, including `k=0` and `s=d`.

## Part III — Multiple dimensions and cyclic coordinates

### Exercise 21 — Flattening a grid

A row-major grid has `R` rows and `C` columns. Derive flattening and unflattening in both bases. For `R=3,C=4`, translate zero-based cell `(2,1)` and one-based cell `(3,2)`. Explain why a valid flattened index does not by itself validate a supplied pair `(r,c)`. What must be checked before allocating `R*C` elements?

### Exercise 22 — Rectangular sums

Let `P[r][c]` contain the sum of the first `r` rows and first `c` columns of a zero-based grid. Derive the dimensions, zero border, recurrence, and formula for rectangle `[r0,r1) × [c0,c1)`. Translate a one-based inclusive query `[R0,R1] × [C0,C1]` into those prefix coordinates. Explain why the prefix table has an extra row and column.

### Exercise 23 — Neighbors and borders

For a zero-based `R × C` grid, derive bounds checks for the four orthogonal neighbors without evaluating an unsigned subtraction too early. Repeat for one-based coordinates. How many cells have all four neighbors? Handle dimensions `0,1,2` explicitly before giving a general formula.

### Exercise 24 — Circular stepping

A ring has capacity `C > 0`. Derive how to move a valid index forward by `k >= 0` positions in either base. Work out `C=5`, starting at zero-based 4 or one-based 5, with steps `0,1,5,7`. Give a C-like implementation that avoids overflow in `i+k` and in the addition after reducing `k` modulo `C`.

### Exercise 25 — Queue with one unused slot

A ring buffer has `C >= 2` physical slots. `head` is the next read index, `tail` the next write index. One slot is deliberately left unused. Derive empty, full, and occupancy formulas; maximum usable capacity; and push/pop updates. For `C=5,head=3,tail=1`, list occupied slots. Why can equal indices not mean both empty and full without additional state?

### Exercise 26 — Queue with a count

Redesign the queue using `head` and `count`, allowing all `C > 0` slots to be used. Derive the next write position, empty/full conditions, and state updates. What is the next write coordinate when full, and why must you not write there? Give an overflow-safe expression for occupancy-based wrapping and trace `C=1`.

### Exercise 27 — Splitting work evenly

Distribute `n` elements among `p > 0` workers, giving the first few workers one extra element when necessary. Derive each worker's start, end, and length. Prove that ranges meet exactly, cover every element once, and differ in size by at most one. Compute `n=10,p=3` and `n=3,p=5`. Express each worker's selection in one-based coordinates, including empty workers.

### Exercise 28 — Counting nested loops

Derive the number of iterations, not just the complexity class:

```c
for (size_t i = 0; i < n; ++i)
    for (size_t j = i + 1; j < n; ++j)
        visit(i, j);
```

Repeat with `j=i` initially. Derive corresponding one-based loops. For `n=4`, list every pair for the strict version. Explain why the closed-form count can overflow even when each individual index fits.

### Exercise 29 — Counting subarrays

For a sequence of length `n`, count nonempty contiguous subarrays using pairs of boundaries. Count empty subarrays if empty selections at different boundaries are distinct. Derive the number of subarrays of exact length `w`, where `0 <= w <= n`. Explain why an empty sequence has zero nonempty subarrays but can have one empty selection.

### Exercise 30 — Partition a range around a pivot

You have a nonempty zero-based range `[lo,hi)` and pivot index `m` with `lo <= m < hi`. Express the left and right ranges excluding the pivot, and derive their lengths. Then split the same range into two pieces at `mid = lo + (hi-lo)/2`, without removing any element. Explain why these two uses of a midpoint produce different ranges. Translate both operations into one-based half-open coordinates.

## Part IV — Search, arithmetic, and proofs

### Exercise 31 — Lower bound

Implement lower bound: return the first index whose element is at least `x`, or the end boundary if none exists. Use sorted zero-based data and candidates `[lo,hi)`. State an invariant covering the already excluded elements and a decreasing quantity proving termination. Trace `[2,4,4,7]` with targets `1,4,6,9`, and the empty input. Translate to one-based coordinates, using `n+1` as “not found.”

### Exercise 32 — Upper bound and duplicate counts

Adapt lower bound to return the first element strictly greater than `x`. Use both functions to find the equal-value range and its length. Do this in both bases. Handle an absent value without subtracting one from a zero boundary. Explain why using `hi=mid-1` in the half-open algorithm can skip the answer.

### Exercise 33 — Search for a transition

A predicate on element indices is false followed by true. Return the first true index, or `n`. Derive a binary search that never evaluates the predicate at `n`. Test all-false, all-true, empty, and transition at the final element. Then explain how the result differs from “last false” and how to represent that answer when no false element exists.

### Exercise 34 — Integer capacity audit

All inputs are unsigned sizes bounded by `M`, the largest representable value. Audit these expressions and provide safe alternatives or explicit rejection conditions:

1. `start + count <= n`.
2. `(n + c - 1) / c`, with `c > 0`.
3. `(lo + hi) / 2`, with `lo <= hi`.
4. `rows * cols * sizeof(T)` before allocation.
5. `n + 1` for a prefix table or one-based end sentinel.
6. `i + k` before modulo reduction in a ring.

Distinguish arithmetic representability from whether an allocation actually succeeds.

### Exercise 35 — Strided windows

Windows of width `w > 0` begin at positions `0,s,2s,...`, with `s > 0`, and must fit in `n` elements. Derive their count, last start, and the number of trailing uncovered elements after the final window. Treat `n<w` separately. Work out `(n,w,s)=(11,4,3),(12,4,3),(3,4,2)`. If `s>w`, why is the trailing remainder not the total number of uncovered elements?

### Exercise 36 — Sampled windows with gaps

A window contains `w > 0` samples at offsets `0,d,2d,...,(w-1)d`, with `d > 0`. Successive windows start `s > 0` positions apart. Derive the span, number of valid windows, and mapping from `(window_number, sample_number)` to an element index in both bases. Give an overflow-safe way to determine whether even one window fits before multiplying `(w-1)*d`. Evaluate `n=15,w=4,d=2,s=3`.

### Exercise 37 — Edit-distance table

Let `D[i][j]` be the edit distance between the first `i` characters of one string and the first `j` characters of another. Derive dimensions, initialization, and recurrence for insertion, deletion, and substitution at unit cost. Give the loop bounds and character accesses for zero-based strings and one-based strings. Then compress the table to two rows, stating the meanings of every row entry during the inner loop. Include empty strings.

### Exercise 38 — Partition with three regions

Partition a zero-based array around value `v` using regions:

- `[0,lt)` contains values less than `v`.
- `[lt,i)` contains values equal to `v`.
- `[i,gt)` is unknown.
- `[gt,n)` contains values greater than `v`.

Derive initialization and all three update cases. Explain why the greater-than case does not advance `i`. Prove every access is valid and the loop terminates. Translate the invariant and updates into one-based half-open coordinates. Trace `[3,1,2,3,0]` with `v=2`.

### Exercise 39 — Packed upper triangle

Store only pairs `(i,j)` with `0 <= i < j < n`, ordered by increasing `i`, then increasing `j`. Derive total storage, row length, row start, and the packed offset. List the mapping for `n=5`. Derive the one-based equivalent. Finally recover `(i,j)` from a valid packed offset without a floating-point square root. State the arithmetic checks needed if offsets must fit in `size_t`.

### Exercise 40 — A range API that composes safely

Design an API for a view `(start,length)` into a zero-based sequence of total length `n`. It must support empty views, extracting a subview by local `(offset,count)`, splitting at a local boundary, and converting a nonempty view to one-based inclusive endpoints. It must reject invalid requests without overflowing or dereferencing anything.

1. State a canonical invariant and safe validation order.
2. Derive all operations and explain why accepted intermediate arithmetic is representable.
3. Decide what your inclusive conversion returns for an empty view; do not invent an element.
4. Prove that taking a subview of a subview agrees with taking the equivalent direct subview.
5. Design systematic tests over small `n` that check this composition property, preservation of contents, and all boundary cases.
6. Find counterexamples to these attempted validators: `start+length <= n`; `offset < length`; and `count <= length` alone.

## Solutions

### Solution 1

| Length | Zero-based elements | One-based elements | Boundaries | Final boundary label |
|---:|---|---|---:|---:|
| 0 | none | none | 1 | 0 |
| 1 | 0 | 1 | 2 | 1 |
| 2 | 0, 1 | 1, 2 | 3 | 2 |
| 7 | 0 through 6 | 1 through 7 | 8 | 7 |

For nonempty sequences the last indices are `n-1` and `n`. When `n=0`, neither `-1` nor `0` denotes an element in its respective representation. With unsigned arithmetic, `n-1` also wraps. A boundary exists even when no elements do.

### Solution 2

The lists are respectively `3,4,5,6,7` (5), `3,4,5,6,7,8` (6), `4,5,6,7,8` (5), and `4,5,6,7` (4).

For integer endpoints `a <= b`, counts are `b-a`, `b-a+1`, `b-a`, and `max(0,b-a-1)`. Both half-open forms naturally represent an empty interval with equal endpoints; the fully open form does too. Closed `[a,a]` is a singleton. Half-open intervals are especially convenient because adjacent pieces share one endpoint and lengths are simple differences.

### Solution 3

The straight path has 11 segments; the circular fence has 12. A straight sequence has `max(n-1,0)` neighboring pairs. A circle with `n >= 3` has `n` connecting segments because the last post connects back to the first. Do not use unsigned `n-1` for the empty straight case without a guard.

### Solution 4

Element 7 becomes element 8. `[3,8)` contains zero-based elements 3 through 7, so it becomes inclusive `[4,8]` or half-open `[4,9)` in one-based element coordinates.

Boundary 12 still means “12 elements precede this point.” If represented as the coordinate of a hypothetical next element, it becomes 13. That coordinate is a sentinel, not an existing element. Translate based on a variable's meaning, not just the base of the surrounding code.

### Solution 5

For `k>0`, the last index is `s+k-1`; the exclusive endpoint is `s+k`. These formulas work in either element-coordinate base. At `k=0`, there is no last element, but the exclusive endpoint equals the start.

A zero-based view is valid exactly when `s <= n && k <= n-s`, with left-to-right short-circuit evaluation. Only after that check may you safely compute `s+k`: it is bounded by the already representable `n`. This permits `(s,k)=(n,0)`.

### Solution 6

The results are `[5,7)` of length 2, empty at 5, empty, and empty at 4. Compute `lo=max(a,c)` and `hi=min(b,d)`. If `lo < hi`, return `[lo,hi)` with length `hi-lo`; otherwise return `(lo,0)` as a start-and-length empty result, or `[lo,lo)`. Check the order before subtracting with unsigned integers. A disjoint intersection has no uniquely required empty-location label; the API must choose a convention.

### Solution 7

The domain is `0 <= p <= n`. Zero-based pieces are `[0,p)` and `[p,n)`, with lengths `p` and `n-p`. One-based inclusive pieces are `[1,p]` and `[p+1,n]`, with an explicit empty flag or length when either piece is empty; reversed inclusive endpoints are only a convention, not actual element accesses.

For `n=5`: at 0 the pieces have lengths 0 and 5; at 2 they have lengths 2 and 3; at 5 they have lengths 5 and 0. For `n=0`, only `p=0` is valid and both pieces are empty.

### Solution 8

Require `1 <= k <= n`. The zero-based index is `n-k`; the one-based index is `n-k+1`. For length 8 the answers are `(7,8)`, `(5,6)`, and `(0,1)`. Subtracting the extra one confuses a one-based ordinal `k` with a zero-based offset. For `k=1`, the correct zero-based index already is `n-1`.

### Solution 9

Zero-based local `j` has `0 <= j < hi-lo`; its array index is `lo+j`. An array index `i` in the range becomes `i-lo`.

For nonempty inclusive `[L,R]`, one-based local `t` has `1 <= t <= R-L+1`; its array index is `L+t-1`, and the inverse is `i-L+1`. A zero-based local offset `j` instead maps to `L+j`, with `0 <= j < R-L+1`. Carry a length separately if the selection may be empty.

### Solution 10

| Loop | n=0 | n=1 | n=4 | General count |
|---|---|---|---|---|
| A | 0 | 0,1 | 0,1,2,3,4 | n+1 |
| B | none | none | 1,2,3 | max(n-1,0) |
| C | none | 0 | 0,1,2,3 | n |
| D | none | 1 | 1,2,3,4 | n |
| E | 0 | 0,1 | 0,1,2,3,4 | n+1 |

C correctly traverses zero-based elements; D correctly traverses one-based elements. A and E visit all zero-based boundary labels, which is valid if the operation is on boundaries rather than elements. B omits the first zero-based element or the last one-based element, depending on the intended base.

### Solution 11

The original loop reaches `i=n-1` and reads `a[n]`. At zero length, `n-1` wraps and the loop enters despite there being no elements.

```c
for (size_t next = 1; next < n; ++next)
    compare(a[next - 1], a[next]);
```

The two indices are valid because `1 <= next < n`. This also avoids overflowing `i+1` in a loop condition.

```lua
for next = 2, n do
    compare(a[next - 1], a[next])
end
```

Both execute `max(n-1,0)` comparisons.

### Solution 12

```c
for (size_t remaining = n; remaining > 0; ) {
    --remaining;
    use(a[remaining]);
}
```

The variable counts elements not yet visited. Before decrement it is in `1..n`; after decrement it is in `0..n-1`. The loop never decrements zero. In the original, `i>=0` is always true for an unsigned variable, and initial or eventual subtraction wraps.

```lua
for i = n, 1, -1 do use(a[i]) end
```

Nonnegativity gives only a lower bound. Valid zero-based access also requires `i<n`.

### Solution 13

Partners are `n-1-i` and `n+1-i`. There are `floor(n/2)` swaps.

```c
for (size_t i = 0; i < n / 2; ++i)
    swap(a[i], a[n - 1 - i]);
```

The body cannot execute for `n=0`, so its subtraction is safe. Lua-like code is:

```lua
for i = 1, n // 2 do
    swap_at(a, i, n - i + 1)
end
```

Here `swap_at` exchanges two table entries; it is a helper, not Lua's standard library. Swap counts for the requested lengths are `0,0,1,2,3`. For length 5, zero-based pairs are `(0,4),(1,3)`; the middle index 2 stays in place.

### Solution 14

Insertion requires `0 <= p <= n < C` and backing storage for `C` elements. The unused slot `a[n]` exists even though it is not yet part of the logical sequence.

```c
for (size_t i = n; i > p; --i)
    a[i] = a[i - 1];
a[p] = value;
++n;
```

Move rightward from the end so a source is read before being overwritten. Deletion requires `d<n`:

```c
for (size_t src = d + 1; src < n; ++src)
    a[src - 1] = a[src];
--n;
```

`d+1` is representable because `d<n`. The old final slot is no longer logically part of the sequence.

```lua
-- Require 1 <= q <= n+1 and room for n+1 elements.
for i = n, q, -1 do a[i + 1] = a[i] end
a[q] = value
n = n + 1

-- Independently: require 1 <= r <= n.
for src = r + 1, n do a[src - 1] = a[src] end
a[n] = nil
n = n - 1
```

Empty insertion performs no shift and writes the first slot. Singleton deletion performs no shift and leaves length zero. For fixed-width arithmetic, reject insertion if the new length or coordinate cannot be represented.

### Solution 15

The required capacity is mathematically `k+1`; the terminator is at zero-based index `k`. Test `k < C`, which both proves there is room and avoids computing an overflowing `k+1`. Assume the source has `k` readable bytes and copying is otherwise valid.

The four cases are reject, accept with terminator at 0, accept with terminator at 3, reject. An empty terminated string still needs one byte. A zero-capacity buffer cannot store even its terminator.

### Solution 16

Let `L=b-a`. If `L=0`, the count is zero and there is no last index. Otherwise the count is `1+(L-1)/s`, with integer division; the last index is `a+(count-1)*s`. An alternative count is `L/s + (L%s != 0)`, which also handles zero.

The examples visit `2,6,10` (3), `2,6,10,14` (4), and nothing (0). Avoid `(L+s-1)/s` unless the addition is checked. A naive `i+=s` loop can overflow after its last valid visit; a count-controlled loop or a checked final increment avoids that separate bug.

### Solution 17

The chunk count is `q=n/c + (n%c != 0)`. Valid chunk numbers satisfy `j<q`. For such a chunk, `start=j*c`, `length=min(c,n-start)`, and `end=start+length`. The one-based inclusive endpoints are `start+1` and `end`.

For `(10,4)`, ranges are `[0,4),[4,8),[8,10)`, with lengths 4,4,2. For `(8,4)`, there are exactly two full chunks. For `(0,4)`, there are none. `n/c+1` invents an extra chunk on exact multiples, including zero. Products for valid chunk starts are bounded by `n`; still validate `j` before multiplying.

### Solution 18

If `w<=n`, the count is `n-w+1`. Starts are `0..n-w` or `1..n-w+1`. Otherwise the count is zero; do not subtract `w` from unsigned `n` first.

For length 5 and width 3, zero-based windows are `[0,3),[1,4),[2,5)`; one-based versions are `[1,3],[2,4],[3,5]`. An exact-fit window has one start. A coherent zero-width convention places an empty window at each boundary, giving `n+1`; that count may require a wider type when `n` is maximal.

### Solution 19

Allocate `n+1` prefix entries, set `P[0]=0`, and compute `P[i+1]=P[i]+a[i]` for `0<=i<n`. The sum of `[l,r)` is `P[r]-P[l]`, with `0<=l<=r<=n`.

For one-based data and a zero-keyed prefix table, use `P[0]=0` and `P[i]=P[i-1]+a[i]` for `i=1..n`. Inclusive `[L,R]` sums to `P[R]-P[L-1]`.

For an entirely one-based prefix table, define `Q[t]` as the sum of the first `t-1` elements. Set `Q[1]=0`; compute `Q[i+1]=Q[i]+a[i]`; query with `Q[R+1]-Q[L]`.

The empty one-based selection can be represented with a start `L` and count zero, or conventionally `R=L-1`, for `1<=L<=n+1`; both formulas then subtract the same prefix entry. Check prefix-size representability and use a sum type that can hold the accumulated values.

### Solution 20

Require `s<=n && k<=n-s` and `d<=n && k<=n-d`. A forward copy is safe if the destination begins at or before the source, or begins at/after its exclusive end. Only `s<d<s+k` requires backward movement. After validation, `s+k` is safe.

```c
if (s < d && d < s + k) {
    for (size_t t = k; t > 0; ) {
        --t;
        a[d + t] = a[s + t];
    }
} else {
    for (size_t t = 0; t < k; ++t)
        a[d + t] = a[s + t];
}
```

The example ends as `[A,A,B,C,D]`. A forward copy there would propagate `A` into every destination. Zero length touches nothing; equal starts perform harmless self-assignments. In production C, `memmove` supplies overlap-safe byte copying, but byte-count multiplication must also be checked.

### Solution 21

For zero-based coordinates require `0<=r<R` and `0<=c<C`; flatten as `r*C+c`. Given `0<=k<R*C`, recover `r=k/C`, `c=k%C`. The valid-index requirement ensures `C>0` when unflattening.

For one-based coordinates, flatten to a one-based index with `(r-1)*C+c`. Recover from `k` using `r=(k-1)/C+1`, `c=(k-1)%C+1`. The example yields zero-based 9 and one-based 10.

For `C=4`, the invalid zero-based column 4 in `(0,4)` produces flattened offset 4, which is a valid offset belonging to `(1,0)`. Validate each coordinate independently. Check element-count multiplication and then byte-count multiplication before allocation; zero-sized dimensions have no valid cells and must not reach division by zero.

### Solution 22

The prefix grid has `(R+1) × (C+1)` entries. Set `P[0][c]=0` and `P[r][0]=0`. For `1<=r<=R`, `1<=c<=C`:

```text
P[r][c] = a[r-1][c-1] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]
```

The query is:

```text
P[r1][c1] - P[r0][c1] - P[r1][c0] + P[r0][c0]
```

Require `0<=r0<=r1<=R` and `0<=c0<=c1<=C`. Empty rectangles give zero. One-based inclusive endpoints map to zero-based boundaries `r0=R0-1, r1=R1, c0=C0-1, c1=C1`. Prefix coordinates count consumed rows and columns; zero consumed needs storage too. Check both added dimensions and their product, and use arithmetic whose intermediate sums and differences are representable.

### Solution 23

For an already valid zero-based cell: up exists if `r>0`, down if `r<R-1`, left if `c>0`, right if `c<C-1`. Only evaluate `r-1` or `c-1` after the corresponding positive check. Since the cell is valid, `R` and `C` are positive, making `R-1` and `C-1` safe here.

For one-based cells, conditions are `r>1`, `r<R`, `c>1`, `c<C`. Compute neighbor coordinates after the check. If either dimension is below 3, no cell has all four neighbors. Otherwise the count is `(R-2)*(C-2)`. A zero dimension means there is no cell to begin with.

### Solution 24

Mathematically the zero-based answer is `(i+k)%C`; the one-based answer is `((i-1+k)%C)+1`. Reduce `t=k%C`, then wrap without a potentially overflowing sum:

```c
// Preconditions: C > 0, i < C.
size_t t = k % C;
size_t result = (t >= C - i) ? t - (C - i) : i + t;
```

In the addition branch `i+t<C`, so the sum is representable. For one-based input, run this on `i-1`, then add one; the answer is at most `C`. The requested zero-based results are `4,0,4,1`; one-based results are `5,1,5,2`.

### Solution 25

Empty means `head==tail`. Full means `next(tail)==head`, where `next(i)` returns 0 at `i=C-1`, otherwise `i+1`. Occupancy is:

```text
tail-head             if tail >= head
(C-head)+tail          otherwise
```

The second branch is less than `C` because `tail<head`. Maximum occupancy is `C-1`. Push only if not full: write at `tail`, then advance it. Pop only if not empty: read at `head`, then advance it.

For `C=5,head=3,tail=1`, the occupied slots are `3,4,0`, giving occupancy 3. If all slots were usable, advancing the write index around the ring would produce equal indices both before any writes and after `C` writes. A count or full flag would be needed to distinguish those states.

### Solution 26

Maintain `head<C` and `0<=count<=C`. Empty means `count=0`; full means `count=C`. The next write position is mathematically `(head+count)%C`, computed using Solution 24 with step `count`. Reduce first because `count` can equal `C`.

Push requires `count<C`: write at that position, then increment count. Pop requires `count>0`: read at head, advance head, and decrement count. When full, the write coordinate equals head; it names the oldest occupied slot, not free space.

At `C=1`, head and the next write coordinate are always zero. Count alternates between 0 and 1. The count carries all empty/full information, and no slot is wasted.

### Solution 27

Let `q=n/p`, `r=n%p`. For worker `j` with `0<=j<p`:

```text
length(j) = q + (j < r ? 1 : 0)
start(j)  = j*q + min(j,r)
end(j)    = start(j) + length(j)
```

`start(0)=0`; subtracting consecutive starts gives exactly `length(j)`, so pieces meet without gaps or overlap. The final endpoint is `p*q+r=n`. Lengths are only `q` and `q+1`. Valid products and sums above are bounded by `n`.

For `(10,3)`: `[0,4),[4,7),[7,10)`. For `(3,5)`: `[0,1),[1,2),[2,3),[3,3),[3,3)`. One-based nonempty pieces are inclusive `[start+1,end]`; retain a count for empty pieces. One-based half-open notation is `[start+1,end+1)`, requiring representability of the end sentinel.

### Solution 28

Strict pairs total `(n-1)+(n-2)+...+0 = n(n-1)/2`, with count zero for `n=0`. Including the diagonal gives `n(n+1)/2`. One-based loops use `i=1..n`, with `j=i+1..n` for strict pairs and `j=i..n` for diagonal-inclusive pairs, under the stated representability assumptions.

At `n=4`, strict pairs are `(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)`. There are quadratically many pairs even though indices grow only linearly. Divide the even factor before multiplying to reduce intermediate overflow, but still check the final product. Guard the zero case before computing unsigned `n-1`.

### Solution 29

Each nonempty subarray corresponds to two distinct boundaries `l<r` among `n+1` boundaries, giving `n(n+1)/2`. Empty selections correspond to `l=r`, giving `n+1` distinguishable positions. Including both kinds gives `(n+1)(n+2)/2` mathematically.

For exact length `w`, choose `l` with `0<=l<=n-w`; there are `n-w+1` possibilities. This also gives `n+1` for `w=0`. With `n=0`, the only pair is `(0,0)`, so there is one empty selection and no nonempty selection.

### Solution 30

Excluding the pivot produces `[lo,m)` of length `m-lo`, and `[m+1,hi)` of length `hi-m-1`. Their lengths sum to `hi-lo-1`.

Splitting without removal produces `[lo,mid)` and `[mid,hi)`, with lengths `floor((hi-lo)/2)` and `ceil((hi-lo)/2)`. The element at `mid`, if present, belongs to the right piece. Confusing these operations silently discards or duplicates an element.

For one-based half-open `[L,H)` and pivot `M`, use `[L,M)` and `[M+1,H)`. A split uses `[L,B)` and `[B,H)`, where `B=L+(H-L)/2`. The arithmetic depends on interval semantics, not on the base.

### Solution 31

```c
size_t lower_bound(const int *a, size_t n, int x) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < x)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}
```

Invariant: `0<=lo<=hi<=n`; every element before `lo` is less than `x`; every element at or after `hi` is at least `x`. The unresolved elements lie in `[lo,hi)`, while the final boundary answer may be anywhere in `[lo,hi]`. When the loop executes, `lo<=mid<hi`, so access is valid. Each update strictly decreases `hi-lo` without making it negative. At equality there are no unresolved elements, and the invariant identifies the correct boundary.

For `[2,4,4,7]`, results for `1,4,6,9` are `0,1,3,4`. The `(lo,hi)` traces are:

- Target 1: `(0,4) → (0,2) → (0,1) → (0,0)`.
- Target 4: `(0,4) → (0,2) → (0,1) → (1,1)`.
- Target 6: `(0,4) → (3,4) → (3,3)`.
- Target 9: `(0,4) → (3,4) → (4,4)`.

Empty input immediately returns 0.

```lua
local lo, hi = 1, n + 1
while lo < hi do
    local mid = lo + (hi - lo) // 2
    if a[mid] < x then lo = mid + 1
    else hi = mid end
end
return lo
```

One-based answers are `1,2,4,5`; empty input returns 1. The sentinel `n+1` is never read because `mid<hi<=n+1`. It must still be representable.

### Solution 32

Change the condition to `a[mid] <= x`: those elements belong before the desired upper boundary. Let the two answers be `lb` and `ub`; the equal-value range is `[lb,ub)` and its length is `ub-lb` in either base's half-open coordinates. In one-based inclusive notation it is `[lb,ub-1]` only when `lb<ub`; otherwise report empty explicitly.

For `[2,4,4,7]` and `x=4`, zero-based boundaries are `(1,3)` and one-based boundaries `(2,4)`, both giving count 2. An absent target gives equal boundaries and count zero.

In the half-open algorithm, `hi=mid` excludes `mid` from future reads while retaining it as a possible answer boundary. `hi=mid-1` excludes that answer too. With `[1,3]` and target 3, starting at `(0,2)` gives `mid=1`; the wrong update sets `hi=0` and returns 0 instead of 1. It can also underflow at `mid=0`.

### Solution 33

Use the same bounds and midpoint as Solution 31. If `predicate(mid)` is true, set `hi=mid`; otherwise set `lo=mid+1`. The invariant says indices before `lo` are false and indices at/after `hi` are true. Since `mid<hi<=n`, the predicate is never called at `n`.

All-false returns `n`; all-true returns 0 when nonempty; empty returns 0 without a call; transition at the final element returns `n-1`. If the first true boundary is `b>0`, the last false element is `b-1`. If `b=0`, no false element exists: return an optional result or `(found,index)`, not an unsigned subtraction. An all-false nonempty input has last false `n-1`, even though there is no true element.

### Solution 34

1. Check `start<=n && count<=n-start`; only then add.
2. Use `n/c + (n%c != 0)`. Division requires `c>0`.
3. Use `lo+(hi-lo)/2`, which stays between the validated bounds.
4. If `cols!=0 && rows>M/cols`, reject. Otherwise form `elements=rows*cols`. If `elements>M/sizeof(T)`, reject; otherwise form the byte count. Assume `sizeof(T)>0`.
5. Require `n<M` before forming `n+1`. For prefix storage, check the subsequent byte multiplication too. A one-based sentinel can fail to fit even when all element indices fit.
6. Reduce `k%C`, then use the conditional-wrap calculation in Solution 24, with `C>0` and `i<C`.

Passing these checks proves only that integer expressions are representable. It does not prove memory is available, that the object exists, that a pointer is valid, or that an allocator succeeded. Signed overflow is not a substitute for checked arithmetic either.

### Solution 35

If `n<w`, there are no windows; no last start exists, and all `n` elements are uncovered. Otherwise let `A=n-w`. The count is `q=A/s+1`; the last start is `(q-1)*s`; the trailing count is `n-(last+w)=A%s`.

For `(11,4,3)`, starts are `0,3,6`, count 3, trailing count 1. For `(12,4,3)`, starts are also `0,3,6`, trailing count 2. For `(3,4,2)`, there are no windows and all 3 elements are uncovered.

If `s>w`, internal gaps of `s-w` elements occur between successive windows, so the trailing count omits those gaps. With at least one window, the total uncovered count in that case is `(q-1)*(s-w) + trailing`. For `s<=w`, windows overlap or meet, so there are no internal gaps.

### Solution 36

The span is `E=(w-1)*d+1`: this is the distance between first and last sample, plus one. If `n<E`, there are no windows. Otherwise `q=(n-E)/s+1`.

With zero-based window number `t` and zero-based sample number `j`, the index is `t*s+j*d`, with `0<=t<q`, `0<=j<w`. If both numbers and the data indices are one-based, the mapping is `(t-1)*s+(j-1)*d+1`, with `1<=t<=q`, `1<=j<=w`.

To check fit without overflow: first reject `n=0`; then test `w-1 <= (n-1)/d`. Because `w,d>0`, the subtractions/division are valid. Only if this holds compute the product and span; both are bounded by `n`. For `n=15,w=4,d=2,s=3`, `E=7`, count 3, starts `0,3,6`; sampled indices are `{0,2,4,6}`, `{3,5,7,9}`, `{6,8,10,12}`. Position 12 is the last sample; indices 13 and 14 trail it.

### Solution 37

For string lengths `m,n`, dimensions are `(m+1) × (n+1)`. Initialize `D[i][0]=i` and `D[0][j]=j`. For `i=1..m`, `j=1..n`:

```text
D[i][j] = min(
    D[i-1][j] + 1,
    D[i][j-1] + 1,
    D[i-1][j-1] + cost
)
```

For zero-based strings, `cost=(a[i-1] != b[j-1])`; for one-based strings, `cost=(a[i] != b[j])`. Prefix lengths remain `i,j` in both cases. A table state is a pair of lengths, not a pair of character indices.

With two zero-keyed rows, initialize `prev[j]=j` for `j=0..n`. For each `i=1..m`, set `curr[0]=i` and compute columns `1..n` using `prev[j]`, `curr[j-1]`, and `prev[j-1]`. During column `j`, `prev` holds the complete row `D[i-1][*]`, while `curr[0..j-1]` holds the completed current prefix. After the inner loop, swap the rows. Return `prev[n]` after all rows; if `m=0`, the initialized row already is the answer.

If table storage must also be entirely one-based, store logical `D[i][j]` at physical `[i+1][j+1]`; shift row-buffer indices similarly. Check dimensions and arithmetic, including temporary `+1` candidates, not just the final distance.

### Solution 38

```c
size_t lt = 0, i = 0, gt = n;
while (i < gt) {
    if (a[i] < v) {
        swap(a[lt], a[i]);
        ++lt;
        ++i;
    } else if (a[i] > v) {
        --gt;
        swap(a[i], a[gt]);
    } else {
        ++i;
    }
}
```

The invariant includes `0<=lt<=i<=gt<=n`. The loop condition implies `i<n`; in the less case `lt<=i`, so both accesses are valid. In the greater case, old `gt>i>=0`, so decrementing is safe and the new `gt` is a valid element index. The swapped-in element from the unknown suffix has not been classified: advancing `i` would skip it. The unknown length `gt-i` decreases by exactly one each iteration. Empty input exits immediately.

Trace, showing state after each operation:

```text
[3,1,2,3,0]  lt=0 i=0 gt=5
[0,1,2,3,3]  lt=0 i=0 gt=4
[0,1,2,3,3]  lt=1 i=1 gt=4
[0,1,2,3,3]  lt=2 i=2 gt=4
[0,1,2,3,3]  lt=2 i=3 gt=4
[0,1,2,3,3]  lt=2 i=3 gt=3
```

For one-based coordinates initialize `lt=i=1`, `gt=n+1`. Regions become `[1,lt)`, `[lt,i)`, `[i,gt)`, `[gt,n+1)`. Use the same updates and loop condition, assuming the sentinel fits. When finished, `[lt,gt)` is the equal region; the algorithm need not preserve order within a region.

### Solution 39

There are `T=n(n-1)/2` elements mathematically, with `T=0` for `n<2`. Row `i` has `n-i-1` entries. Its start is the sum of preceding row lengths:

```text
S(i) = i*(2*n-i-1)/2
K(i,j) = S(i) + (j-i-1)
```

For `n=5`, the mapping is:

| Packed offset | Pair |
|---:|---|
| 0 | (0,1) |
| 1 | (0,2) |
| 2 | (0,3) |
| 3 | (0,4) |
| 4 | (1,2) |
| 5 | (1,3) |
| 6 | (1,4) |
| 7 | (2,3) |
| 8 | (2,4) |
| 9 | (3,4) |

For one-based `1<=I<J<=n`, the one-based packed index is `S(I-1)+(J-I)`. To invert a zero-based `k<T`, locate the unique row `i` in `0..n-2` satisfying `S(i)<=k<S(i+1)`; then `j=i+1+(k-S(i))`. Binary search the strictly increasing boundary sequence `S(0)..S(n-1)`, where `S(n-1)=T`. Equivalently find its first entry greater than `k` and subtract one from that boundary's index. Such an entry exists and cannot be the first, so that subtraction is safe. For a one-based packed index, first subtract one and add one to the recovered coordinates.

Do not evaluate `2*n` blindly. A safer formulation is `S(i)=T-tri(n-i)`, where `tri(x)=x*(x-1)/2` and `tri(0)=0`. To calculate `tri(x)`, handle `x<2`, divide the even factor by two, then reject if the remaining multiplication would exceed the integer maximum. If `T` fits, these smaller triangular values also fit. Validate the pair before calculating its offset, and check the byte count separately before allocation.

### Solution 40

Use the invariant `start<=n && length<=n-start`. Evaluate the first condition before subtraction. This includes the empty view at `start=n` and excludes any view starting beyond the sequence, even an empty one.

A subview request is valid when `offset<=length && count<=length-offset`. Then return `(start+offset,count)`. The new start is at most `start+length<=n`, and the new end is at most the old end, so accepted additions fit whenever `n` fits.

A split at local boundary `p` requires `p<=length` and returns `(start,p)` and `(start+p,length-p)`. Empty left and right pieces are permitted. For a nonempty view, one-based inclusive endpoints are `(start+1,start+length)`. Nonemptiness implies `start<n`, so even `start+1` is safe when `n` is maximal. For an empty view, return an explicit empty result carrying its boundary label `start`; do not form `start+1` merely to invent inclusive endpoints.

For composition, suppose `(o,c)` is a valid subview request and `(u,v)` is valid inside that subview. The nested result is `(start+o+u,v)`. Since `u<=c<=length-o`, we know `o+u<=length`; and since `v<=c-u<=length-(o+u)`, the direct request `(o+u,v)` is valid and yields the same range. The proof establishes safe arithmetic before the code adds offsets.

A systematic test strategy:

1. For each `n` from 0 through a small bound such as 8, construct data whose element values equal their original indices.
2. Enumerate every valid `(start,length)`, including length-zero views at every boundary.
3. Enumerate every valid `(offset,count)` inside each view and every valid second-level `(u,v)`. Compare nested and direct view coordinates and extracted contents.
4. Enumerate every split boundary; concatenating the two selected contents must recover the original view, and their lengths must sum to its length.
5. Exercise invalid starts, lengths, offsets, and counts just beyond each limit, plus values near the machine maximum. Invalid requests must fail before subtraction, addition, or access that would be unsafe.
6. For every nonempty inclusive conversion, verify that converting back recovers the same start and length. Empty conversion must remain explicitly empty.

Counterexamples:

- `start+length<=n` can accept wrapping arithmetic: in an unsigned 8-bit arithmetic model, `start=250,length=10,n=10` wraps the sum to 4. In real C, use values near `SIZE_MAX` with `size_t`; small integer types may be promoted before addition.
- `offset<length` rejects the valid empty subview at `offset=length,count=0`, including the sole subview of an empty view. It also says nothing about whether a positive count fits.
- `count<=length` accepts `length=5,offset=4,count=2`, even though the requested end is outside the view. The available suffix is `length-offset`, not the entire length.

The recurring proof obligation is concrete: identify what each number counts, establish its legal domain, and show each accessed index falls inside the allocated object. Choosing zero-based or one-based coordinates changes translations; it does not remove the need to distinguish elements, boundaries, and counts.