Time Complexity: O(2*N), where N is the size of the array. This is because we are iterating through the array once to build the hash array and then iterating through the hash array to find the repeating and missing numbers.

Space Complexity: O(N), as we are using an additional hash array of size N+1 to store the frequency of each element.

Optimal Approach 1

Algorithm

First, calculate the sum of all elements in the given array, denoted as S, and the sum of natural numbers from 1 to N, denoted as Sn. The formula for Sn is (N * (N + 1)) / 2.
Now calculate S - Sn. This gives us X - Y, where X is the repeating number and Y is the missing number.
Next, calculate the sum of squares of all elements in the array, denoted as S2, and the sum of squares of the first N numbers, denoted as S2n. The formula for S2n is (N * (N + 1) * (2N + 1)) / 6.
Now calculate S2 - S2n. This gives us X2 - Y2.
From the equations S - Sn = X - Y and S2 - S2n = X2 - Y2, we can compute X + Y by the formula (S2 - S2n) / (S - Sn).
Using the values of X + Y and X - Y, we can solve for X and Y through simple addition and subtraction.
Finally, return the values of X (the repeating number) and Y (the missing number).

Code