An array Data[1:20] contains 20 integers that may include duplicate values. A program is needed to create a new array Unique that contains only the distinct...

(a) The algorithm must iterate through every element in Data[1:20] and check whether it already appears in a growing Unique array. If the element has not been seen before, it is added to Unique and the counter is incremented. [6]

DECLARE Data : ARRAY[1:20] OF INTEGER
DECLARE Unique : ARRAY[1:20] OF INTEGER
DECLARE UniqueCount : INTEGER
DECLARE i : INTEGER
DECLARE j : INTEGER
DECLARE IsDuplicate : BOOLEAN

UniqueCount ← 0

FOR i ← 1 TO 20
    IsDuplicate ← FALSE
    FOR j ← 1 TO UniqueCount
        IF Data[i] = Unique[j] THEN
            IsDuplicate ← TRUE
        ENDIF
    NEXT j
    IF IsDuplicate = FALSE THEN
        UniqueCount ← UniqueCount + 1
        Unique[UniqueCount] ← Data[i]
    ENDIF
NEXT i

OUTPUT "Number of unique values: ", UniqueCount

The outer loop visits each element of Data in turn [1]. The inner loop scans all values already stored in Unique to test for a duplicate [1]. The flag IsDuplicate records whether a match was found [1]. Only when no match is found is the value appended and the counter advanced [1]. Initialising UniqueCount to 0 ensures the inner loop does not execute on the first element, so the first value is always added [1].

(b) Trace for the first 5 elements of the input array [4, 7, 4, 2, 7, ...]: [3]

The first two elements are new, so both are added [1]. When 4 is encountered again it matches Unique[1], so it is skipped [1]. The value 2 is new, but the second 7 matches Unique[2] [1].

(c) Best case: UniqueCount = 1, which occurs when all 20 elements hold the same value. Worst case: UniqueCount = 20, which occurs when every element is different. [1]