Keep a deficient interval of possible values and only the array segment containing occurrences from that interval. This is missing-value search by deficient value intervals:
def missing(): Int = {
  val n = a.length
  var lo = 0L
  var hi = n.toLong + 1L
  var l = 0
  var r = n
  while (hi - lo > 1L) {
    val p = lo + (hi - lo) / 2L
    val k = partition(l, r, p.toInt)
    if ((k - l).toLong < p - lo) {
      hi = p
      r = k
    } else {
      lo = p
      l = k
    }
  }
  lo.toInt
}
The precondition is that every original entry lies in . The loop invariant is
together with: every active entry lies in , and every original occurrence with a value in that interval is in the active segment. The whole array remains a permutation of its initial contents. Initially these assertions follow from the precondition and .
After array partitioning, the low subinterval has occurrences and possible values. If it is deficient, retaining it preserves the loop invariant. Otherwise , while the original active count is strictly less than ; subtraction gives
Thus the high subinterval is deficient and retaining it also preserves the loop invariant. Discarded occurrences lie outside the new candidate interval. The loop variant is the positive integer , which strictly decreases because the midpoint is strictly internal. At exit the interval has one possible value and fewer than one occurrence, so lo is absent from the entire original array. For the loop is skipped and zero is returned. The Long value bounds avoid overflowing ; every internal pivot is at most , so its checked mathematical range fits Int.
For the time complexity, let be the interval width and its active occurrence count before iteration . The loop invariant gives , and binary search gives . Each two-way array partition costs . Until the width reaches one, the widths are bounded by , so the total scan work is bounded by a geometric series plus loop overhead: overall, hence for positive . Partitioning the full array again at every iteration would instead lose this bound. Auxiliary space complexity is .
Search for the predecessor of the matching linked list node, or for the last linked list node if there is no match. This helper makes deletion uniform:
class LinkedBook extends Book {
  private val header = new Node("", "", null)

  // Pre: name != null.
  // Post: result is header or a real node.
  // All real nodes through result have names different from name.
  // result.next is null or has name equal to name.
  // No state is changed.
  private def findPrev(name: String): Node = {
    require(name != null)
    var p = header
    while (p.next != null && p.next.name != name) {
      p = p.next
    }
    p
  }

  def store(name: String, number: String): Unit = {
    require(name != null && number != null)
    val p = findPrev(name)
    if (p.next == null)
      p.next = new Node(name, number, null)
    else
      p.next.number = number
  }

  def recall(name: String): String = {
    require(name != null)
    val p = findPrev(name)
    require(p.next != null, "Name is not in the book")
    p.next.number
  }

  def isInBook(name: String): Boolean = {
    require(name != null)
    findPrev(name).next != null
  }

  def delete(name: String): Boolean = {
    require(name != null)
    val p = findPrev(name)
    if (p.next == null) false
    else {
      p.next = p.next.next
      true
    }
  }
}
The search loop invariant says that p is the header or a reachable real linked list node, and every real linked list node from the start through p has a name different from the requested name. The linked list has not been changed. Short-circuit evaluation protects p.next.name when the end is reached. The loop variant is the number of real linked list nodes strictly after p; finiteness and acyclicity make it a nonnegative decreasing integer. Consequently the helper's stated postcondition holds.
For store, a found name changes only its number; an absent name adds exactly one fresh binding at the end, maintaining uniqueness. For delete, unlinking the found linked list node removes exactly the requested binding; absence returns false without mutation. Both query operations preserve the abstraction function. Non-null preconditions are checked at entry; recall additionally checks membership using the one completed search, avoiding a redundant whole-list membership scan. The helper is the only additional operation and its complete behavioral contract is stated above.
Keep the same player until an occupied, in-range cell is supplied:
val board = new Chomps(6)
var player = 1
while (board.Count() > 0) {
  board.Display()
  var x = -1
  var y = -1
  while (!board.Legal(x, y)) {
    println("Player " + player + ": enter x, then y")
    try {
      x = scala.io.StdIn.readInt()
      y = scala.io.StdIn.readInt()
    } catch {
      case _: NumberFormatException =>
        x = -1
        y = -1
    }
    if (!board.Legal(x, y)) println("Choose an occupied cell")
  }
  board.Move(x, y)
  if (board.Count() == 0)
    println("Player " + player + " loses; player " + (3 - player) + " wins")
  else player = 3 - player
}
The outer loop invariant is that player is the next player's number, either one or two, and the board is the result of the accepted moves. The inner loop invariant says that the board and player have not changed; rejected inputs do not consume a turn. Assuming the input source continues and eventually supplies a legal coordinate pair, the inner loop finishes. No program can guarantee that a user stops entering illegal moves, so that interaction assumption is necessary.
Every accepted move removes at least its selected token, so the outer loop variant is Count(), a decreasing nonnegative integer. In a nonempty order ideal, is occupied. Removing it removes the entire board, whereas a move at any other cell leaves it. Therefore the player making the final move is exactly the loser; the code reports that player before changing the turn. At most legal moves occur.
Programming language polymorphism lets one expression or operation work with values of different types or concrete representations. In object-oriented programming, subtype polymorphism lets a reference of an interface or superclass type designate instances of different implementing software classes. A call through that reference uses dynamic dispatch to select the receiver's overriding object method. For example, a routine taking Book can invoke recall on a linked-list or an array-based implementation while depending only on the common abstract contract.
Parametric polymorphism is another form: the type parameter in FiniteDist[T] lets the same interface describe distributions over Booleans, integers or characters. A generic method introduces a further type parameter when its output type differs. Method overloading, in contrast, supplies several statically selected signatures with one name; it should not be confused with receiver-dependent dynamic dispatch. Correct substitutability also requires implementations to respect the common behavioral contract, not merely to share method names.
The inclusive interval is nonempty exactly when . Reject with a failed precondition, rather than assigning a nonexistent normalization to an empty interval. Compute its width in Long before taking a reciprocal:
class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
  require(l <= u, "Empty uniform interval")
  private val width = u.toLong - l.toLong + 1L
  private val mass = 1.0 / width.toDouble

  def getProb(x: Int): Double =
    if (l <= x && x <= u) mass else 0.0

  def getDom: List[Int] = {
    var x = l.toLong
    var rev = List.empty[Int]
    while (x <= u.toLong) {
      rev = x.toInt :: rev
      x += 1L
    }
    rev.reverse
  }
}
The loop invariant says that and rev contains exactly the integers in reverse order. The loop variant is while the guard is true. Long handles both the full interval width and the increment past Int.MaxValue. At exit, reversing yields each support value once. All support values have mass , so their exact sum is one; Double approximates that rational number. Very large valid domains require correspondingly large lists and sufficient memory; that resource issue does not make the mathematical endpoint values invalid.
Use the conventional integer calling convention: $a0 holds the argument and $v0 holds the result. The function is recursive, so every call must preserve its own return address and original argument. The first recursive result must also survive the second call; a caller-saved register alone would not protect it.
This implementation reserves a 32-byte stack frame, keeping the stack pointer eight-byte aligned. Offsets 0–15 are available as the outgoing argument area, 16 stores the original argument, 20 stores the first result, 24 is padding, and 28 stores the return address. It changes no callee-saved register. Assemble in classic MIPS delayed-branch mode with instruction reordering disabled, such as .set noreorder.
foo:
addiu $sp,$sp,-32  # allocate 32-byte aligned frame
sw $ra,28($sp)  # save caller return address
sw $a0,16($sp)  # save original n
beq $a0,$zero,foo_base
sll $zero,$zero,0
addiu $t0,$zero,1
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $t0,$zero,2
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $a0,$a0,-1
jal foo
sll $zero,$zero,0
sw $v0,20($sp)  # preserve foo(n-1) across next call
lw $a0,16($sp)  # recover original n
sll $zero,$zero,0
addiu $a0,$a0,-3
jal foo
sll $zero,$zero,0
lw $t0,20($sp)
sll $zero,$zero,0
addu $v0,$v0,$t0  # combine the two recursive results
beq $zero,$zero,foo_return
sll $zero,$zero,0
foo_base:
addu $v0,$a0,$zero  # base case result is n
foo_return:
lw $ra,28($sp)
sll $zero,$zero,0
addiu $sp,$sp,32  # release the frame
jr $ra
sll $zero,$zero,0
All displayed operation mnemonics denote single machine instructions. In particular, sll $zero,$zero,0 is the actual harmless shift encoding often abbreviated by the pseudoinstruction nop; addu $v0,$a0,$zero performs a copy without the move pseudoinstruction. Each branch or jump has an explicit harmless branch delay slot, and harmless shifts also separate loads from their subsequent uses. The base cases return the original argument; other calls return the sum of the two recursive values. Every return restores the saved return address and exactly undoes the stack allocation.[ref]
The stated domain is nonnegative integer , with sufficient stack space and a result representable in the intended integer type. The non-trapping additions implement that mathematical result within range; beyond it, machine wraparound would require a separately specified integer semantics.
Divide the divisibility relation by to obtain . Since , multiplication by the modular multiplicative inverse gives . Therefore all integer solutions are , .
Modulo , the choices give
They are distinct residue classes: equality of two such classes would imply , hence . Every integer is congruent to one of those thirteen choices, so the list is exhaustive.
Take . These are four distinct positive integers and . Their products are and , whose difference is , so . Here the correct reduced modulus is , and indeed . The example illustrates why cancelling a noninvertible factor may change the modulus in modular arithmetic.
Let , , and . The preceding part gives . The integer congruence on the left is equivalent to
By Euclid's lemma, coprimality of and makes this equivalent to . The reverse implication is also immediate by multiplying a divisibility relation by . Therefore
This is cancellation of a common factor in a congruence. The printed equality sign in the right-hand expression is interpreted as equality of residue classes, hence the displayed integer congruence. Ordinary equality of the integers would be false: the following example has .
Let , and write , with positive integers . If an integer divided both and , then would divide both and , contradicting the maximality of their greatest common divisor . Thus . Equivalently, Bézout's identity for can be divided by to express as an integer combination of .
The contrapositive is that an integer perfect square has residue or modulo . Let for an integer . If is an even number, then . If is an odd number, then . These exhaust the possible parities of an integer. Thus a residue of or excludes being a perfect square, as required by the contrapositive.
Suppose, for a proof by contradiction, that an integer is both an even number and an odd number. Then and for some integers . Subtracting yields . The left side is an integer, while is not. This contradiction proves that no integer is both even and odd.
Fix any seven-element subset . Its power set supplies pigeons. Map each subset to its integer sum. Since the elements are positive, all such sums lie between and . The latter is at most the sum of the seven largest available elements,
There are therefore at most possible sums, fewer than the subsets. The pigeonhole principle forces two distinct subsets to have the same sum. Every seven-element subset has the two-sum property. This is the subset-sum pigeonhole bound. The weaker estimate would also suffice, since .
The number is
A direct search over every -element subset must inspect candidates. Testing one candidate by generating its subset sums creates values; storing previously seen sums detects a collision. Generating them incrementally needs arithmetic operations, or for the straightforward independent calculation of each sum. Thus the simple overall search has cost on the scale of , apart from integer-arithmetic and data-structure costs.
The important time complexity distinction is that fixed gives polynomial growth in , of degree , but this can still become impractically large. If increases with , both the candidate count and the internal power set can grow exponentially. For example, near the binomial coefficient is already exponentially large. An exhaustive implementation can therefore encounter a combinatorial explosion; the fixed- estimate must not be described as exponential in .
For , independence gives
The initial factor accounts for the shift by one; substituting accounts for doubling the random variable. Its support consists of positive odd integers.
Conditioning on has positive probability exactly when for an integer . This is the same event as . The addition of independent Poisson random variables gives a Poisson distribution with parameter for the sum. Therefore, for ,
Thus . The case is a constant zero random variable. For even, nonpositive, or noninteger , the conditioning event has zero probability, so an event-conditional probability distribution is not specified by the quotient formula. This is a two-component case of Poisson-multinomial conditioning.
Insert the Poisson distribution probability generating function into the preceding bound:
For fixed , differentiate the exponent with respect to . Its derivative is , and its second derivative is , so its unique minimum occurs at . At that value,
Consequently
This Chernoff bound remains valid for noninteger positive thresholds ; the event is then the same as exceeding or equalling its integer ceiling.
Because , the function is increasing and nonnegative. Thus . Applying Markov's inequality to the nonnegative random variable , whose expected value is finite by assumption, yields
Under the usual probability generating function convention takes nonnegative integer values. The argument itself works for any real random variable if is understood as the finite expected value .
There are three unnumbered cases inside this leaf.
For the nine-child recurrence, a recursion tree has subproblems of size about . There are constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence . This is also the first case of the master theorem, since and the additive work is constant.
For the decrementing recurrence, summing from the supplied base at three gives
so here as well. Values at the smaller base indices remain one as specified.
For the recurrence that squares its recursive result, set . Then above the base range. Let
After expansions, , giving the exact answer
For powers of two this is . For arbitrary positive integer , the exact values form plateaux: , while . In general . It is not uniformly over integer : near the top of a plateau the exponent is closer to . Keeping the integer halving is essential; the ordinary linear master theorem does not apply to squaring .