Let denote the non-null nodes reachable from the head. The representation invariant requires a finite acyclic null-terminated linked list and pairwise distinct names among its reachable nodes. Names and numbers retain the interface's string data type interpretation; no ordering of names is required.
The abstraction function is the finite partial function
Name uniqueness makes this a function, rather than a relation assigning multiple numbers to one name. Initially list == null, so and the abstract book is empty. Unreachable allocated nodes are outside this abstract state.
For each table index , let be the set of non-null nodes reachable by following next. A sufficient representation invariant is:
  • The array has exactly buckets, and every bucket heads a finite acyclic linked list.
  • The sets are pairwise disjoint, so one physical node cannot belong to two buckets.
  • Every reachable node has a valid user identity, lies in bucket hash(node.user), and has both counters between zero and Int.MaxValue.
  • User identities are unique among all reachable nodes, not merely within a single chain.
The abstraction function maps these nodes to the total functions of part (a): if the unique node for exists, and are its fields; otherwise both are zero. A stored record with two zero counters is harmless and has the same observable meaning as an absent record. This intentionally permits multiple concrete representations of the same abstract program state.
Initially every bucket is null, so the representation invariant holds and the abstraction function yields all zeros. The successful-update branch preserves every structural condition; the insertion branch creates a fresh node with a previously absent identity in its correct bucket. Both branches realize exactly the incoming-increment postcondition, demonstrating correct operations through an abstraction function.
The following method belongs inside the source class and uses the helper from part (d). It preserves the existing outgoing count, and a newly encountered user starts with exactly one incoming and zero outgoing payments.
def recordIncoming(user: Int): Unit = {
  require(1 <= user && user <= 99999999, "invalid user identity")
  val bucket = hash(user)
  val p = find(user, table(bucket))
  if (p == null) {
    table(bucket) = new PaymentsHash.Node(user, 1, 0, table(bucket))
  } else {
    require(p.countIn < Int.MaxValue, "incoming count is full")
    p.countIn += 1
  }
}
On a hit, exactly one field is incremented after the overflow check. On a miss, inserting at the bucket head preserves all existing records and gives precisely the required change from implicit zero to one. The given hash function must return an index in consistently for a given user. Its actual formula is not needed by this method. The nested private node class is accessible to its companion class in Scala, so retaining the source's PaymentsHash.Node visibility is valid.[ref]
Inside the supplied PaymentsHash class, scan until a matching node or the end of the chain. A null return means the user has no record in this bucket.
private def find(user: Int, head: PaymentsHash.Node): PaymentsHash.Node = {
  var p = head
  while (p != null && p.user != user) p = p.next
  p
}
The loop invariant says that every node already passed has a different user identity and p heads the unexamined suffix. Short-circuit evaluation of && prevents dereferencing null. The representation invariant supplies an acyclic finite chain, so each unsuccessful step shortens that suffix and proves algorithm termination. The code changes no node fields.
With a directly indexed array, use two parallel count arrays, or one array of count records, at each user identity. Both queries and increments take running time, with no hash collision. However, reserving positions for each of two four-byte counters uses about million bytes, roughly MiB before object overhead, even when only a few users have payments. Index zero is unused and all valid positions initially contain zero.
With a linked list, store one node (user, countIn, countOut, next) for each active user. A scan locates a record, returning zero counts if absent; an increment creates a missing record or updates its counter. Storage is for stored users, but a query or update can require running time. Nodes also carry pointer and allocation overhead and lack direct indexed access.
With a hash table using separate chaining, compute a hash bucket from the user identity and store its record in that bucket's linked list. The same zero-default convention applies to a missing record. With buckets and a well-distributing hash function, the expected operation cost is in terms of the load factor of a hash table; worst-case cost remains under severe collisions. Storage is , but a permanently fixed cannot maintain constant expected cost as grows without bound. A good distribution and, where permitted, hash table resizing address that trade-off.
Every operation requires . The queries have postconditions “return ” and “return ” respectively, leaving both functions unchanged. An incoming increment additionally requires and has
The outgoing increment analogously requires , increments only , and preserves . These frame conditions prevent an implementation from accidentally changing another user's count. Here a subscript zero denotes the old program state.
trait Payments {
  // All methods require 1 <= user && user <= 99999999.
  // Queries leave the abstract state unchanged.
  def incoming(user: Int): Int
  def outgoing(user: Int): Int

  // Require the corresponding old count < Int.MaxValue.
  // Increment only that user's named count by one.
  def recordIncoming(user: Int): Unit
  def recordOutgoing(user: Int): Unit
}
The preconditions and postconditions are part of the formal specification; the trait's type signatures alone cannot express all of them. The implementation below uses checked require calls for the relevant invalid operations.
Use an abstract data type with two total count functions, , where and . counts incoming payments and outgoing payments. Initially for every valid user. A user without a stored record is therefore observable as two zero counts; no separate registration operation is necessary.
The explicit bound matches the source's Int record fields. Increment operations require space in the relevant count, so no integer overflow is permitted. An unbounded mathematical counting abstract data type would instead require an arbitrary-precision representation or an explicit overflow policy. The large user domain does not require allocating a record for every user: a sparse map with a default value can realize these total functions.
To preserve the actual printed function, including its handling of nonpositive exponents and wrapping Int bases, use a tail-recursive accumulator with the same multiplication order:
def anotherfuncRec(x: Int, n: Long): Double = {
  require(x > 0)
  @scala.annotation.tailrec
  def loop(y: Int, i: Long, result: Double): Double = {
    if (i <= 0) result
    else {
      val nextResult = if (i % 2 == 1) result * y else result
      loop(y * y, i / 2, nextResult)
    }
  }
  loop(x, n, 1.0)
}
Each recursive call corresponds to one source iteration and carries exactly its next program state. Hence it reproduces the printed numerical behavior, rather than silently repairing it. For positive n, both routines use steps; for nonpositive n, both take constant time. The recursive call is in tail position, so Scala's tail-call optimization avoids a growing call stack; the annotation asks the compiler to check that condition.
If the intended exact power is required instead, change the base and accumulator parameters of this same recurrence to BigInt and require n >= 0, as in part (d). Its mathematical loop invariant becomes a recursion invariant, with the same logarithmic number of multiplication steps.
The algorithmic intention is exponentiation by squaring to compute for . With exact arithmetic, its loop invariant is
Initially result = 1, y = x, and i = n. For an even integer , squaring y and replacing i by preserves the product. For an odd integer , first multiply result by y; then . The nonnegative loop variant i decreases by halving whenever positive. At exit , so the loop invariant yields result = x^n. There are multiplication steps.
Two qualifications are essential for the actual source. There is no requirement that n be nonnegative: for every n <= 0 the printed function simply returns 1.0. Also, var y = x infers Int, so y *= y uses wrapping integer arithmetic, while the accumulator uses floating-point arithmetic. For example, anotherfunc(50000, 2L) returns -1794967296.0, rather than 2500000000.0. An exact-power loop invariant cannot prove a false claim about that execution.
More precisely, for positive n, after iterations the remaining exponent is , and the Int base is the signed 32-bit representative of modulo . The accumulator multiplies those signed representatives for the set bits of n, in increasing bit order, with a floating-point rounding after each multiplication. This describes the actual code even when the intended power law fails. In an exact implementation, use a nonnegative-exponent precondition and arbitrary-precision integers, for example:
def powerExact(x: Int, n: Long): BigInt = {
  require(x > 0 && n >= 0)
  var result = BigInt(1)
  var y = BigInt(x)
  var i = n
  while (i > 0) {
    if (i % 2 == 1) result *= y
    y *= y
    i /= 2
  }
  result
}
The displayed loop invariant applies exactly to this version. It performs logarithmically many arbitrary-precision multiplications; their bit cost grows with operand size, so that statement is not an bit-complexity bound. Merely making the accumulator a Double does not widen the separate Int base variable.
Under exact integer arithmetic, the intended result is , using the ceiling function. A sufficient loop invariant is
Initially , and the final disjunction is true. If the guard holds, the old value is below . Incrementing i and doubling y therefore preserves and makes the new lower bound true. At exit . If , positivity of forces ; otherwise . Both cases establish the claimed postcondition. Doubling eventually reaches or exceeds any fixed positive , proving algorithm termination in this arithmetic model. This is the doubling-loop ceiling logarithm argument.
The printed Scala implementation is not correct for its entire stated Int domain. Its y is an Int. For , it reaches , wraps to on the next doubling, then becomes zero and stays zero. The guard remains true forever. The loop invariant above is valid for the printed code only when . Scala documents Int as a signed 32-bit value equivalent to Java's primitive int.[ref]
A corrected implementation for every positive Int input widens the doubling variable before any multiplication:
def ceilingLog2(x: Int): Int = {
  require(x > 0)
  var i = 0
  var y = 1L
  while (y < x.toLong) {
    i += 1
    y *= 2L
  }
  i
}
Now at most 31 iterations are needed and , safely within Long. The same loop invariant proves total correctness without the overflow gap.
Validate the complete input before doing the addition. The arrays use most-significant-digit-first positional notation. The result has one extra leading position, which contains either zero or the final carry.
def binaryAddition(x: Array[Int], y: Array[Int]): Array[Int] = {
  require(x != null && y != null, "arrays must not be null")
  require(x.length == y.length, "lengths must match")
  val n = x.length
  var k = 0
  while (k < n) {
    require((x(k) == 0 || x(k) == 1) &&
            (y(k) == 0 || y(k) == 1), "digits must be 0 or 1")
    k += 1
  }
  val answer = new Array[Int](n + 1)
  var carry = 0
  var j = n - 1
  while (j >= 0) {
    val column = x(j) + y(j) + carry
    answer(j + 1) = column % 2
    carry = column / 2
    j -= 1
  }
  answer(0) = carry
  answer
}
A failed require throws IllegalArgumentException, covering mismatched lengths, invalid binary digits and null arrays. The largest column sum is three, so the carry always lies in . The binary-addition carry invariant says that the already processed input suffixes equal the written result suffix plus the carry shifted to the next column. After the final column, placing that carry at position zero proves the returned value is the sum. Neither input array is modified. Equal empty inputs are accepted as zero and return Array(0); the specification imposes no positive-length restriction. Running time and result storage are .
Repeated integer division by two generates the binary digits from least significant to most significant. Reverse the accumulated characters once, and treat zero separately.
def binaryCon(n: Int): String = {
  require(n >= 0, "n must be nonnegative")
  if (n == 0) return "0"
  var remaining = n
  val digits = new StringBuilder
  while (remaining > 0) {
    digits.append(if (remaining % 2 == 0) '0' else '1')
    remaining /= 2
  }
  digits.reverse.toString
}
Zero produces "0"; positive inputs produce a binary number without leading zeros. No library routine performs the number-to-base conversion. Appending to the builder and reversing once gives linear work in the number of binary digits and uses that much output storage.
Search only the suffix strictly after each candidate first index. This enforces distinct indices even when the target is twice an existing value. Compute the complement in Long to prevent integer overflow: subtracting two Int values can require 33 signed bits.
def twoSum(a: Array[Int], target: Int): (Int, Int) = {
  def lowerBound(from: Int, wanted: Long): Int = {
    var lo = from
    var hi = a.length
    while (lo < hi) {
      val mid = lo + (hi - lo) / 2
      if (a(mid).toLong < wanted) lo = mid + 1
      else hi = mid
    }
    lo
  }
  var i = 0
  while (i < a.length - 1) {
    val wanted = target.toLong - a(i).toLong
    val j = lowerBound(i + 1, wanted)
    if (j < a.length && a(j).toLong == wanted) return (i, j)
    i += 1
  }
  (0, 0)
}
The outer loop invariant says that no solution has a smaller first index than i, when a pair is written in increasing index order. A failed suffix binary search proves there is no partner for the current i, extending the excluded prefix by one. A successful return has and in exact integer arithmetic. At exhaustion, every possible ordered pair has been excluded, so the sentinel (0,0) means no solution. The inner loop invariant is the standard lower-bound partition, restricted to the suffix starting at i + 1.
There are at most suffix searches, each taking running time, so the total is , customarily written for . Auxiliary space is . Empty and singleton arrays immediately return the sentinel. This is distinct-index two-sum by suffix lower bounds; a faster two-pointer technique is also possible on a sorted array, but the code here directly meets the requested search-based bound.
For the given sorted array, the complete lower-bound search behavior is for , for , for , and for . In particular, index is never the correct answer because the two equal entries share the same first insertion position.
These unit tests cover every value boundary, equality case and missing-value interval:
  • Below all entries, including the smallest machine integer: ternarySearch(a, Int.MinValue) == 0 and ternarySearch(a, 0) == 0.
  • Equality with the first entry: ternarySearch(a, 1) == 0.
  • Values in the first gap: ternarySearch(a, 2) == 1 and ternarySearch(a, 3) == 1.
  • Repeated equality must return the first duplicate: ternarySearch(a, 4) == 1.
  • Values in the second gap: ternarySearch(a, 5) == 3 and ternarySearch(a, 9) == 3.
  • Equality with the final entry: ternarySearch(a, 10) == 3.
  • Beyond the final entry: ternarySearch(a, 11) == 4 and ternarySearch(a, Int.MaxValue) == 4.
For every tested target, also assert that the array is unchanged, the result lies in , every entry before it is strictly smaller, and every entry from it onward is at least the target. These postconditions check the intended partition directly rather than merely accepting any equal occurrence.
This is lower-bound search: return the first position whose value is at least the target, allowing the result to equal the array length. The notation for an empty suffix is vacuously true, so this also covers a target larger than every entry and the empty array. Assume a stable sorted array, ordered nondecreasingly.
def ternarySearch(a: Array[Int], x: Int): Int = {
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val third = (hi - lo) / 3
    val m1 = lo + third
    val m2 = hi - 1 - third
    if (a(m1) >= x) hi = m1
    else if (a(m2) < x) lo = m2 + 1
    else {
      lo = m1 + 1
      hi = m2
    }
  }
  lo
}
The loop invariant is
Initially the excluded prefix and suffix are empty, so both quantified assertions hold. During an iteration, . If , sortedness makes every later value at least , so replacing hi by m1 preserves the right assertion. If the first test failed and , every earlier value is below , so replacing lo by m2 + 1 preserves the left assertion. Otherwise ; both new exclusions are valid, and lo = m1 + 1; hi = m2 retains exactly the unresolved middle. In that branch , since a single value cannot satisfy both strict and nonstrict inequalities in opposite directions.
The nonnegative loop variant hi - lo strictly decreases. In fact, with old length and , the three possible new lengths are , with the middle branch feasible only when nonnegative; each is at most . At exit lo == hi, and the loop invariant is exactly the desired partition. The result is the unique lower-bound index, including the first equal entry when duplicates occur. This ternary lower-bound search uses comparisons and auxiliary space, in the Big O notation word-operation model. The index formulas also avoid computing an overflowing 2 * length.
The proposed condition is not a loop invariant at the loop head. It holds initially and on entry to every executed body, but the iteration starting with i == 10 finishes with i == 11. Control then returns to the condition with the proposed upper bound false. A suitable numerical loop invariant is . If the number of printed lines matters, strengthen it to “exactly lines have been printed.” At exit, this and i > 10 give exactly ten printed lines. The nonnegative loop variant decreases by one on every iteration.
A loop invariant is a property of the program state that holds whenever control reaches the loop's condition, including the final failed test. Its main purpose is proving partial correctness: establish it initially, prove one guarded iteration preserves it, then combine it with the negated condition to obtain the postcondition. A separate loop variant or another progress argument proves algorithm termination and hence total correctness.
Recursively partition into equal halves by rank, keeping the selected median in the lower half:
quantiles(A,k):
    if length(A) == k:
        return [maximum(A)]
    p = select the (length(A)/2)-th smallest element of A
    L = all elements of A at most p
    R = all elements of A greater than p
    return quantiles(L,k) followed by quantiles(R,k)
All elements are distinct, so both halves have exactly elements. Since remains a power of two, every internal split occurs at a rank divisible by .
For correctness, the desired ranks in the lower half are . In the upper half they are the same local multiples of , shifted by . These are exactly all desired global ranks. At a leaf of size , its maximum is its sole requested local rank. Induction therefore proves that the output contains every requested order statistic, in increasing order, including the original maximum. There is no separate internal-node output of p, which would duplicate a rank already supplied by the lower subtree.
Use a worst-case linear-time selection algorithm and linear partitioning. The divide-and-conquer algorithm has
There are internal levels, each with total work , and leaves with total work . Since the source assumes , the running time is
This is multiselection by balanced rank partitioning. In-place selection and partitioning can use the original array; the output has values. The multiselection recursion has depth ; the selection routine contributes its own auxiliary storage.
Let . After each linear-time selection algorithm and partition, exactly elements are removed, so the successive input sizes are . Thus the standard efficient implementation takes
Here selection can use median of medians for worst-case linear time; a suitable randomised linear-time selection routine gives the same bound in expectation. Merely sorting each remaining array would introduce an avoidable logarithmic factor.
, approximately , arithmetic operations. Strassen's algorithm replaces an matrix multiplication by seven products of half-size blocks and a constant number of block additions and subtractions. Consequently
The Master theorem applies with , , since . Padding an arbitrary matrix dimension to the next power of two changes the dimension by less than a factor of two and preserves this asymptotic bound. The cost model counts scalar arithmetic as constant time; it is not a bit-complexity claim for arbitrarily large integer entries.

There are unlisted articles, also show them or only show them.