Use two array indices, advancing only the smaller current entry. Here and in Questions 1–4, code is structured Oberon-style pseudocode: Let be the smallest common value, and let . Existence implies . A useful loop invariant is , , with no common value among the discarded prefixes and . Initially the prefixes are empty. If , then cannot equal any entry of because that sorted array is increasing; it cannot be a common value in the discarded prefix either. Moreover would imply , a contradiction. Thus and incrementing is safe. The other branch is symmetric.
RETURN exits a procedure, Some(x) and None distinguish success and absence, and AND short-circuits from left to right. Arithmetic is exact where the source asks us to ignore integer overflow.PROCEDURE common(a, N, b, M): INTEGER;
VAR i, j: INTEGER;
BEGIN
i := 0; j := 0;
WHILE a[i] # b[j] DO
IF a[i] < b[j] THEN i := i + 1
ELSE j := j + 1
END
END;
RETURN a[i]
END common;Every guard and return therefore uses valid array indices, even without explicit bounds tests. The loop variant decreases on each iteration. At exit the equal entries form a common value no larger than , hence equal . There are at most increments and constant work per increment. The procedure returns the smallest common value in time and auxiliary space.
Replace the existence-dependent bounds proof with explicit bounds tests. Neither input array is changed or copied.The loop invariant is , , and every common value of the original arrays lies in both remaining suffixes and . Equivalently neither discarded prefix contains a common value. Advancing the smaller current value preserves this for the same ordering reason as in part (a).
PROCEDURE commonOrNone(a, N, b, M);
VAR i, j: INTEGER;
BEGIN
i := 0; j := 0;
WHILE (i < N) AND (j < M) DO
IF a[i] = b[j] THEN RETURN Some(a[i])
ELSIF a[i] < b[j] THEN i := i + 1
ELSE j := j + 1
END
END;
RETURN None
END commonOrNone;Both array bounds are checked before any element is read. If the remaining heads are equal, all later entries are larger, so the returned value is the smallest. If either suffix becomes empty, the loop invariant proves there is no common value. The loop variant decreases on each unsuccessful comparison. The result is
Some(smallest common value) or None, with time and auxiliary space, including empty-input cases. A language without short-circuit operators can use nested tests; the guard here itself contains no array reads.The cyclic strict comparisons in the hint identify a head that cannot be the answer:Let be the smallest common value. The loop invariant is , , , and every discarded entry is not common to all three arrays. If , the entry cannot occur in the unprocessed part of , so discard it. The branch has the analogous justification. If neither comparison holds but the heads are not all equal, the hint guarantees , so discard .
PROCEDURE common3(a, N, b, M, c, L): INTEGER;
VAR i, j, k: INTEGER;
BEGIN
i := 0; j := 0; k := 0;
WHILE (a[i] # b[j]) OR (b[j] # c[k]) DO
IF a[i] < b[j] THEN i := i + 1
ELSIF b[j] < c[k] THEN j := j + 1
ELSE k := k + 1
END
END;
RETURN a[i]
END common3;A pointer at its target position cannot be advanced: for example and would imply . Thus all reads stay within array bounds. The loop variant decreases. At exit all heads equal . The cost is time and auxiliary space.
Maintain one array index per input and a candidate value. Cycle through the arrays, counting consecutive agreements with that candidate; when a larger head is encountered, start counting agreements again. The loop invariant has three parts. All indices satisfy ; no discarded entry is common to every input; and every original common value is at least
p is an auxiliary array of indices, not a copy of any input.PROCEDURE commonMany(as, n, m);
VAR p: ARRAY m OF INTEGER;
j, candidate, agree, x: INTEGER;
BEGIN
FOR j := 0 TO m-1 DO
p[j] := 0;
IF n[j] = 0 THEN RETURN None END
END;
candidate := as[0][0];
j := 0; agree := 0;
WHILE agree < m DO
IF p[j] = n[j] THEN RETURN None END;
x := as[j][p[j]];
IF x < candidate THEN
p[j] := p[j] + 1
ELSIF x = candidate THEN
agree := agree + 1;
j := (j + 1) MOD m
ELSE
candidate := x;
agree := 1;
j := (j + 1) MOD m
END
END;
RETURN Some(candidate)
END commonMany;candidate. Additionally, the agree cyclically consecutive arrays immediately preceding index j have heads equal to candidate. These facts are true initially, with an empty agreement run.A head below
candidate is not globally common, by the lower-bound clause, so advancing its pointer is safe. A head above candidate gives a new lower bound: every globally common value lies in this array's unprocessed suffix and so is at least its head. Only this array is yet certified to agree with the new candidate. An equal head extends the run by one. An exhausted suffix proves absence; a run of agreements covers every array exactly once and proves that candidate is common, and the lower-bound clause proves minimality. The exhaustion test precedes each dereference, including after the last entry of a suffix is discarded.For algorithm termination and time complexity, charge comparisons to the pair
(j,p[j]). A fixed entry is discarded at most once, can raise the candidate at most once, and can be counted as an agreement at most once: before the same array is revisited, either the algorithm has finished or the candidate has strictly increased. Thus there are at most three comparisons per input entry, besides the initialization. The result is the smallest common value or None in time and auxiliary space. For , the first head immediately gives the answer. Articles by others on the same topic
There are currently no matching articles.