Write the bit vector as , with the least significant bit. Its unsigned interpretation of a bit string is , where each . The range is the integers from through ; a leading one contributes positive weight , not a sign.
Not injective; its image of a function is exactly . For example, both and give the ceiling function value . Since , , so the value is never attained. For every positive integer ,
Each such interval is nonempty and contained in , with the upper endpoint excluded when . Thus the answer concerning surjectivity depends on the convention for the natural numbers: onto if , and not onto if . The source does not settle that convention.
Pad every number with leading zeros to obtain exactly decimal digits. Its digits are a solution of in nonnegative integers. Conversely every such solution is a valid digit string, since no individual digit can exceed ; its digit sum also excludes the number zero. The stars and bars count therefore gives
For , , so . Thus , with an explicit Big O notation constant and threshold .
False. On every odd positive integer , . Given any proposed Big O notation constant and threshold , choose an odd . Then , contradicting the required bound. The behavior on even integers cannot repair this failure on an unbounded subsequence.
Write for a positive integer moment index. The moment is
This improper integral converges exactly when , namely . For those indices,
At the divergence is logarithmic; for it is a power divergence. Thus, in the source's moment notation, the positive integers allowed are exactly . If , no positive integer moment is finite.
Over integers, choose s = (-), c = flip (-), and a = b = 0. The left fold and right fold both compute the negative of the sum of a finite list. The combining functions differ: s 1 2 = -1, whereas c 1 2 = 1.
Let , using the specified operation . Direct evaluation gives , , , and .
Suppose with the same integer result type. The empty list forces . The two singleton calculations force and . But then
contrary to . No such c,b exist. This is the information restriction in the fold factorisation criterion: equal folded tails must remain indistinguishable after the same head is attached. A larger, function-valued result type can retain the missing information, as the continuation representation of a left fold does below.
For nonnegative integer amount , let be the minimum number of coins making amount . Set and compute, in increasing order of ,
An empty candidate set has minimum . Here denomination ensures that every nonnegative amount is attainable. Removing one coin from an optimal nonempty solution gives a smaller amount, and adding any allowed last coin gives a feasible solution; these two directions prove the recurrence by induction on .
Return whether . This solves the at-most- decision without needing a separate dimension for . The table for the minimum coin change recurrence takes running time and space complexity. The bound is pseudopolynomial time: the amount, rather than its binary encoding length, appears in it. Amount zero needs zero coins.
Accumulate the prefix by Horner's method in base two. digit-'0' converts either permitted digit to its numerical value:
var i = 0
var integerPart = 0.0
while (i < bin.length && bin(i) != '.') {
  integerPart = 2.0 * integerPart + (bin(i) - '0')
  i += 1
}
The loop invariant, in exact arithmetic, is that i is the number of processed digits before the point and
Appending a digit shifts the old positional value by one binary place and adds that digit, which proves preservation. The loop variant is . At exit, i is the binary-point index or the length if no point occurs, and integerPart is the value of the integer prefix. An empty prefix contributes zero. There is one multiplication per processed digit, with no separate powers or repeated divisions. Short-circuit evaluation prevents an out-of-range access when the point is absent.
For Double, this exact-arithmetic invariant describes the intended value; the operational value is the rounded Horner recurrence. Very long prefixes can lose precision or overflow, as discussed in part (g). A fixed-width return type cannot represent every finite binary digit string exactly.
Extract low bits and fill the integer positions from right to left:
var remaining = int_part
var pos = digits - 1
while (pos >= 0) {
  res(pos) = if ((remaining & 1) == 0) '0' else '1'
  remaining = remaining >>> 1
  pos -= 1
}
At the start of an iteration, the loop invariant says that positions contain the correct low bits and
The bitwise AND extracts the remainder modulo two; the shift supplies its quotient. These two facts preserve the loop invariant. The loop variant is . The width established in part (c) ensures that remaining is zero at exit, so the first digits entries encode the whole integer part. For zero the single entry becomes '0'. There are no explicit multiplications or divisions, and no extra digit array is needed.
Generate the fractional bits by repeated doubling, keeping only the unconverted residual:
res(digits) = '.'
var fraction = dec - int_part.toDouble
var out = digits + 1
while (out < res.length) {
  fraction = 2.0 * fraction
  if (fraction >= 1.0) {
    res(out) = '1'
    fraction -= 1.0
  } else res(out) = '0'
  out += 1
}
Let and . The loop invariant is , the first fractional digits have been written, and, in exact arithmetic,
Doubling exposes the next digit, and subtracting that digit leaves the next residual in . This proves preservation. The loop variant is . The loop fills the whole suffix, even when the residual has become zero; subsequent bits are zero. There is one multiplication per output bit. With fractional positions, the result is truncated, with exact-arithmetic error . An integer has an all-zero suffix. No rounding-up step is performed.
Equivalence partitioning divides the input domain into classes expected to exercise the same relevant behavior, then chooses representatives and boundary cases from each class. It is a way to select tests, not a proof that every member of a class must behave identically in a faulty implementation.
Useful classes for this parser include integer-only inputs, a leading point, a trailing point, and digits on both sides; all-zero inputs and inputs containing ones; leading or trailing zeroes; one-digit and longer blocks; and large integer or tiny fractional magnitudes near floating-point rounding, floating-point overflow and floating-point underflow boundaries. For instance, compare '1', '1.', '.1', '1.1', '0001.1000', and digit strings just beyond the exact integer precision of Double. Empty digit blocks have the zero convention used above. If a surrounding validator rejects an entirely empty representation or a bare point, test those as separate invalid-format classes. Unexpected digits and multiple points are likewise validator tests, since the conversion fragments assume well-formed input. Include representatives with independently calculated positional values, rather than relying only on inverse conversion.
The first proposed identity can fail even without numerical error because binary fractions have nonunique textual representations. Leading zeroes, optional points and trailing fractional zeroes are normalized differently by a fixed-width output convention. It also fails if the input has more significant bits than Double can preserve, more fractional places than the output buffer can hold, an integer part outside the assumed Int range, or a value that overflows or underflows during decoding. Array identity here must mean equal contents: a newly allocated Scala array is a different software object, so use sameElements rather than reference equality for a content test.
The second identity fails when the stored fractional precision truncates a nonzero bit; with two fractional places, becomes zero. It can also fail outside the finite nonnegative input and integer-conversion assumptions. Within those assumptions, enough fractional positions to encode the finite Double exactly can permit the round trip, but an arbitrary fixed small width does not guarantee it. Every finite Double has a finite binary expansion; saying that a decimal-looking Double necessarily has an infinite binary expansion would confuse the represented number with an exact decimal real.
The source's introductory example is internally inconsistent: the displayed digit string has value , whereas its shortened character array encodes . The conversion rules above follow the actual input digits. Round-trip testing needs an independent value oracle as well as the two compositions, because two mutually consistent but incorrect routines can conceal each other's errors.
A fixed array containing the distinct seen integers needs capacity at most , because at most one new distinct value is introduced per result entry. Its auxiliary space is therefore , rather than the bitmap's universe storage. A size field identifies the occupied prefix; insertion first checks membership, and appends only when absent.
An unsorted occupied prefix needs linear membership scans, giving total work by the same summation as in the original version. Keeping it sorted permits binary search membership in , but inserting a new value can shift entries, so the overall worst-case upper bound remains quadratic. Unlike a bitmap, the space cost depends on the number of stored values rather than their largest possible numerical magnitude. Compared with part (a)(ii), this extra set array also duplicates information already present in the output prefix; its principal benefit is a separate set interface, not an automatic asymptotic speedup.
The expression constructs a valid iterator object; it does not itself return the concatenated numeric or character values. The element types have a common supertype AnyVal, and covariance lets Iterator[Int] and Iterator[Char] serve as the two inputs to ConcatIterator[AnyVal]. In the ordinary Scala 2 typing of this expression, the common element type is AnyVal. One can make the intended widening explicit:
new ConcatIterator[AnyVal](
  List(1, 2, 3).iterator,
  List('a', 'b', 'c').iterator
)
Successive calls return 1, 2, 3, 'a', 'b', 'c', then exhaustion. Characters remain characters: viewing an existing iterator at a wider type does not convert its contents to integer character codes. No next() is invoked merely by constructing this adapter. The common-type argument uses subtype polymorphism and covariant type parameters, rather than requiring the two concrete input types to be equal.
Use the remainder form of the Euclidean algorithm to compute the greatest common divisor, then divide both components of the fraction by it:
def Reduce(num: Int, den: Int): (Int, Int) = {
  require(0 <= num && num < den)
  var a = den
  var b = num
  while (b != 0) {
    val r = a % b
    a = b
    b = r
  }
  (num / a, den / a)
}
The loop invariant is , , and . Initially it holds by symmetry of the greatest common divisor. For , the integer division identity , with , shows that and have exactly the same common integer divisors. Thus the update preserves the loop invariant. The loop variant is the nonnegative integer , which strictly decreases on each iteration. At exit , so . Dividing by preserves the rational number and makes the returned components coprime. In particular, zero is returned as . No multiplication is needed, and all remainders remain within the original nonnegative Int range.
For a positive remaining fraction , the condition is equivalent to . Since decreases as the positive integer increases, choose . The zero fraction needs no term. This is the greedy Egyptian fraction expansion.
The remaining fraction is
The defining inequalities give . Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.
There are entries in , which contains possible integers. If , then . Therefore some value in is missing, again by the pigeonhole principle. This is an existence conclusion in the chosen interval, not a claim that all missing values lie there; both sides can contain missing values when duplicates occur.
If , the upper side contains the whole permitted range and hence a missing value. If , the condition is impossible. Outside the internal-pivot range this conclusion therefore supplies no improved localization.
For an integer pivot , exactly entries lie in . That interval contains possible integers. If , the pigeonhole principle implies that some value in is missing. Counting occurrences rather than distinct entries only strengthens this argument: occurrences cannot cover more than distinct values.
For completeness, if the lower side contains the entire permitted value range, which already has a missing value. If , the condition is impossible. Thus the general conclusion is a missing permitted value below ; an internal pivot gives useful localization.