An array A contains n integers taken from the interval [0,4n], with repetitions allowed. Describe an efficient algorithm for determining an integer value k that occurs the most often in A. What is the running time of your algorithm? 2. An array A contains n−1 unique integers in the range [0,n−1], that is, there is one number from this range that is not in A. Design an O(n)-time algorithm for finding that number. You are allowed to use additional space besides the array A itself 3. In steps, find the computational complexity of the following loops: (i) for ( c = 1, i = 1 ; i <= n ; i *= 2) for (j =1 ; j <= n ; j++) c++; (ii) for (cc = 1, i = 1 ; i <= n ; i *= 2) for (j = 1; j <= i ; j++) cc++;
