Write for the incoming state and . Use the following explicit contracts.
For add(x), the precondition is and . The postcondition is and for every .
For remove(x), the precondition is and . The postcondition is , with every other count unchanged. This convention rejects removal of an absent occurrence rather than silently treating it as a no-op.
For count(x), the precondition is . The result is and the whole abstract state is unchanged. Counts outside the allowed range are zero in the mathematical total function, but this chosen interface requires an in-range query.
The abstract data type invariant constrains a total count function on integer keys as follows:
The initial state has every count zero, and . These conditions make the abstract state a multiset supported on the allowed finite key range. Since the interface returns an Int, the implementations below use representable nonnegative multiplicities; equivalently add to the invariant, where . The corresponding add precondition below prevents overflow. An idealized unbounded-integer specification can omit that machine bound.
The expected saving on the specified successful searches is
which tends to one iteration as increases. The fractional saving is , which tends to zero. Both versions have logarithmic expected time, and the improvement is a bounded average saving rather than a change of growth rate. A target at the first middle position benefits greatly, but the uniform distribution does not concentrate on that event. The extra equality branch and machine-level costs also matter when comparing measured execution times.
Figure 1.
Early equality return saves less than one iteration on average in perfect search arrays
. Original exact iteration counts and their difference for uniformly chosen present targets in arrays of length . The curves describe loop iterations, not measured execution time. Details.
The expected number is exactly . In the boundary-search version, an interval of length is reduced to length whichever comparison branch is taken. It must therefore take exactly iterations to reduce length to zero, including when a probe has already equaled the target. The result holds for every target in this case, so averaging does not change it.
For an array of size , the first probe finds the uniformly selected target with probability . Otherwise it leaves a half of size ; conditional on entering that half, its target is uniform there. Counting the first iteration in every case gives
For , the successful-search decision tree has targets at depth , requiring iterations. Thus
The numerator is , as follows by induction or by shifting and subtracting a finite geometric sum. Substituting gives
The base gives one iteration, as required.
Return immediately on equality and omit the final array inspection:
def searchEarly(u: Array[Int], z: Int): Boolean = {
  var a = 0
  var b = u.length
  while (a < b) {
    val middle = a + (b - a) / 2
    val value = u(middle)
    if (value == z) return true
    if (value > z) a = middle + 1
    else b = middle
  }
  false
}
An equality returns a genuine matching entry. After a nonequal comparison, descending order excludes the inspected middle entry and one whole side. In the half-open range, setting b = middle already excludes the middle index; subtracting one would incorrectly exclude another possible entry. The candidate interval decreases as before, so absence is reported exactly when no possible entry remains.
Maintain the required boundary between entries strictly above the target and entries at most the target:
def search(u: Array[Int], z: Int): Boolean = {
  var a = 0
  var b = u.length
  while (a < b) {
    val middle = a + (b - a) / 2
    if (u(middle) > z) a = middle + 1
    else b = middle
  }
  a < u.length && u(a) == z
}
The full invariant is , every entry before is greater than , and every entry at or after is at most . The array remains unchanged. Descending order justifies each update: if the middle value is greater, all earlier values are greater too; otherwise all values from the middle onward are at most the target.
The nonnegative loop variant strictly decreases, with each update retaining at most half the old candidate length. On termination , which is the first index whose value could be at most . Equality at that index is therefore necessary and sufficient for presence. Short-circuit evaluation makes the final test safe when , including the empty-array case. The time is , using constant auxiliary space.
The factorization-based version should produce the later outputs faster in this cost model. For an input , it performs at most trial-factor tests and successful divisions, because each successful division removes a factor at least two. The square test uses multiplication, so it does not introduce an extra division on every loop test.
Across all candidates through , the number of costly division or remainder operations is therefore at most
compared with remainder operations for the straightforward routine. Small cases can still be affected by constant overhead; the conclusion concerns the growing enumeration workload, not a promise that every single call is faster.
Remove each prime power as soon as it is found, and stop trial division once the remaining value has no possible smaller factor:
def divisors(n: Int): Int = {
  require(n >= 1)
  var remaining = n
  var factor = 2
  var result = 1
  while (factor.toLong * factor.toLong <= remaining.toLong) {
    var exponent = 0
    while (remaining % factor == 0) {
      remaining /= factor
      exponent += 1
    }
    result *= exponent + 1
    factor += 1
  }
  if (remaining > 1) result *= 2
  result
}
At an outer-loop boundary, write , where is the product of the prime powers already removed. The invariant states that result is , every prime divisor of is smaller than factor, and remaining has no prime divisor smaller than factor. Thus if factor divides remaining, it is prime; a composite factor would have a smaller prime divisor, contrary to the invariant.
During the inner loop, with fixed, . Each division removes one copy, so the positive remainder strictly decreases and supplies an inner-loop variant. On leaving the inner loop the complete power has been removed; multiplying the result by exponent + 1 uses part (d) and reestablishes the outer invariant after advancing factor. The outer factor increases and can never exceed the original while its guard holds, proving termination.
At exit, a remainder greater than one must be prime: a composite remainder would have a prime factor no larger than its square root, which would still be smaller than factor. It therefore contributes one final factor of two. A remainder of one contributes nothing. The algorithm returns using constant auxiliary space and no array. The widened multiplication in the loop guard prevents an Int overflow in the square test.
Every positive divisor has a unique prime factorization with . Conversely every such exponent choice gives a divisor. The exponent choices are independent, so the product rule gives
For the factorization is empty, and the empty product is one, corresponding to the divisor one.
By the time the candidate is emitted, every positive integer has been examined. The straightforward divisor routine makes exactly remainder tests on . Consequently the total number is
and the time is when remainder tests and the other fixed-width operations have constant cost and printing is cheap. Emitting only record candidates does not avoid computing the divisor count of the intervening candidates.
Use a strict record test; tying the previous record is not enough:
def emitHighlyComposite(): Unit = {
  var candidate = 1
  var best = 0
  while (true) {
    val count = divisors(candidate)
    if (count > best) {
      emit(candidate)
      best = count
    }
    candidate += 1
  }
}
At the start of an iteration, best is the maximum divisor count among the positive integers below candidate, taking the maximum of the empty family as zero. The already emitted values are exactly the highly composite numbers in that range, in increasing order. The next count exceeds best precisely when this candidate is a new strict record. Updating the record and advancing the candidate preserves both assertions. The program deliberately has no termination requirement; integer overflow in this unbounded enumeration is ignored as directed by the source.
Test each positive candidate divisor and count the successful remainder tests:
def divisors(n: Int): Int = {
  require(n >= 1)
  var candidate = 1L
  var count = 0
  while (candidate <= n.toLong) {
    if (n.toLong % candidate == 0L) count += 1
    candidate += 1L
  }
  count
}
The loop invariant is and , where denotes candidate. A successful test adds exactly the new divisor; an unsuccessful test leaves the count unchanged. The loop variant is , which decreases by one. At termination , so the returned value is . A Long loop counter prevents the increment after the last positive Int candidate from wrapping around.
Serve customers in nondecreasing service time, with ties broken arbitrarily. The objective in the source includes each customer's own service time, so these are completion times, not only delays before service begins. If the order is , then
To prove optimality, consider adjacent service times after an elapsed time . Their contributions before an exchange are ; after the exchange they are . The total decreases by . Earlier customers are unaffected, and later customers begin after the same combined duration as before, so their completion times are unchanged.
Repeatedly exchanging adjacent inversions reaches a nondecreasing order without increasing the objective. Hence that order is optimal. Sorting takes time in a comparison model, followed by a linear traversal to produce the order or compute the total. Equal service times give zero exchange difference and do not affect optimality. If waiting time were instead defined before service, subtracting the order-independent total service time would give the same optimal order.
Write for , with a separate unit denomination. Choose, among all minimum-coin representations of the target, one whose vector of counts is lexicographically largest when larger denominations come first. Such a choice exists because a fixed positive target has only finitely many representations.
There cannot be two unit coins: replacing them by one decreases the count. For , two copies of can be exchanged using
This keeps the coin count unchanged but increases the first differing larger-denomination count, contradicting the chosen lexicographic maximum. Thus there exists an optimal representation using at most one of each denomination below the largest. The largest denomination may repeat.
It remains to show why that normalization implies greedy optimality; uniqueness alone is not enough for an arbitrary coin system. Fix a denomination . Let be the total value of all coins smaller than in the chosen optimal representation, and let be their number. These smaller coins are distinct. If records the selected non-unit denominations, then
If , replace all smaller coins by one and unit coins. The new number of coins is
contradicting optimality. Therefore the total value below every denomination is strictly less than .
At the largest denomination, this forces its count to be : its residual value is nonnegative and smaller than . Remove those coins. The same smaller-denomination property then forces the next quotient, and so on down to the unit coin. These are exactly greedy's choices, proving greedy is optimal for every positive target. The argument also covers , where the denominations are two and one. Independent comparison with coin-change dynamic programming confirmed the formula for all and targets from one to 2,000; that finite check supplements the proof.
For denominations and target , greedy selects , using three coins. The representation uses two coins and is optimal because there is no denomination six. Hence choosing the largest affordable coin is not generally optimal.
Take reachability to include a path of length zero. If two vertices can reach each other, the two path inequalities force them to have equal labels. Conversely, equal labels force mutual reachability: a missing path in either direction would require a strict inequality. Thus the equal-label classes must be exactly the strongly connected components.
Two different components must also be comparable by reachability. If neither could reach the other, applying the no-path condition in both directions would require both and . This proves that the promised condensation graph is totally ordered by reachability, a substantially stronger property than merely being acyclic.
Compute the components, form the condensation graph, and find a topological order . Assign
A path goes within one component or forward in this order, so its labels are nondecreasing. Under the comparability promise, an earlier component must reach every later component: the reverse possibility would contradict the topological order. Therefore no path from to means that lies in a strictly later component, giving exactly the required strict inequality. This proves both parts of the specification.
For a new example, use vertices , edges . Its components are in that order, and assigning labels works. Every earlier component reaches each later one through the displayed chain.
Figure 1.
An original example whose strongly connected components are ordered by reachability
. This five-vertex example is separate from the examination's two source graphs. Internal cycles receive equal labels; the component chain forces strictly increasing labels between components. Details.
Component computation, scanning original edges to build the condensation graph, topological sorting, and expanding component labels all take . Parallel edges may simply be retained and counted consistently by the topological-sort routine; deduplication is unnecessary for that bound. An empty graph returns the empty mapping.
Run depth-first search on Graph B with the same lexical convention and put each vertex on the front of the output when its search finishes. The finish order is
so the returned topological order is
For example, both edges from point to later entries, the edges from point to and later in the order, and precedes . The construction is valid because in a directed acyclic graph every edge has : a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a directed cycle. Thus reversing the finish order puts every prerequisite before its successor. The time is .
Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) is
Reversing the edges gives outgoing adjacency lists
The second pass first visits only . Its next new root is , whose search visits ; later entries already marked by this search are skipped. The next new root is , whose graph transpose neighbours have already been assigned. Therefore the components are
Within the middle component the directed cycle demonstrates mutual reachability. The source edge structure does not provide return paths from or to . More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes with adjacency lists.[ref]
Use a global clock starting at zero, incrementing once on discovery and once on finish. Scan starting vertices and each adjacency list in increasing numerical order. The first search descends through , returns from , and then visits from . After that search finishes, the unvisited vertex starts a second tree.
A dash denotes a root with no predecessor. is a forward edge: vertex is a proper descendant of , but its predecessor is . Its interval satisfies . is a back edge, because is still an active ancestor when it is examined. The other non-tree edge is also a back edge, while reaches an already finished vertex in a different search tree.[ref]

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