4. Suppose that an array, A, contains n + 1 integers in the range (0, n - 1], with every integer appearing AT LEAST ONCE, so that ONE of the numbers duplicated. Design an efficient algorithm for finding the duplicate integer, and discuss its runtime complexity. Full credit will be given for an algorithm that is linear. DO NOT USE ANY PROGRAMMING LANGUAGE SPECIFIC INSTRUCTIONS OR BUILT IN FUNCTIONS (like a max function, for example). YOU MUST DEVELOP YOUR ALGORITHM USING BASIC ARITHMETIC OPERATIONS. (10 points) KEY IDEA Algorithm Duplicate Number (A, n) Input: An array of integers, A, whose length is n + 1, and whose elements are in the range [0.n-1), with one integer appearing twice Output: The integer in the interval [0, n - 1] that is duplicated in A PROCESS