Given a sorted array of integer, A, with possible duplicate elements. (a) Implement an efficient function in ?ava to find in A, the numbers of occurrences of the input value k For example, in an array A--1, 2, 3, 5, 6, 6, 6, 9, 10 and k- 6, your program should return 3. (b) What is the running time complexity of your function? Justify. The input is a square, N by N, matrix of nonnegative integers with possible duplicate elements. Each individual row is a strong decreasing sequence from left to right. Each individual column is a stronq decreasinq sequence from top to bottom Implement in Java an o(N) worst-case algorithm that decides if a number x is in the matrix and, if x is present, prints how many times. Note: Please include in the header of your Java program (using comments) the main ideas of your algorithm. Example of the 4 x 4 matrix: 26 22 17 10 19 16 12 7 12 10 74 Example of the output for this matrix and x7 Number 7 found in the matrix 2 times" (a) Implement a sublinear running time complexity recursive function in Java public static long exponentiation(long x, int n) to calculateX". Note: In your function you can use only the basic arithmetic operators (+,, ,%, and /). (b) What is the running time complexity of your function? Justify (c) Give a number of multiplications used by your function to calculate x63