3. (20 marks) There are numbers from 1 to n in an array A. Out of these, one of the number gets duplicated and one is missing. (a) (10 marks) Design an algorithm to find out the duplicate number. For example, let n be 7 and array A be {3, 5, 2, 6, 1, 7, 6 }, the answer should be 6. You have to do it in O(n) time without using any auxiliary space (array, etc..). Justify your solution (why your algorithm is (n)). Give the pseudo code description of your algorithm and analyze its time complexity. (b) (10 marks) Implement your algorithm using Java. Your program takes any valid sequence of numbers as the input, outputs the repeating number.