Problem Statement: Given an array arr[ ] of size N, each integer from the range [1, N] appears exactly once except A which appears twice and B which is missing. The task is to find the numbers A and B.

Examples:

Input: arr[ ] = {2, 1, 2}
Output: Missing = 3, Repeating = 2
Explanation: In the array,
3 is missing and 2 occurs twice.

Input: arr[ ] = {2, 1, 2, 3, 4}

Output:

A = 2 (Repeating)
B = 5 (Missing)

Input: arr[ ] = {5, 3, 4, 5, 1}

Output: A = 5 (Repeating)
B = 2 (Missing)

Approach: Our approaches should be having Time Complexity O(n).

So, let's do it with natural numbers concepts.

I am assigning an array. Let's say, arr = [ 1, 2, 2, 3, 4 ]

We have to find A(Repeating Value) and B (Missing Value).

Step 1: From the sum of first N natural numbers,

SumN = 1 + 2 + 3 + … + N = (N (N + 1)) / 2

So, SumN= (1+2+3+4+5)= (5(5+1))/2 =15. [Here N=5]

We took 1st 5 natural numbers because in our Array there are 5 numbers.

And, let the sum of all the array elements be Sum.

Sum= (1+2+2+3+4)=12.

Now,

SumN = Sum - A + B

A -B = Sum - SumN

So, A-B = 12 -15 → A-B= -3 → Equation 1.

And from the sum of the squares of first N natural numbers,

SumSqN = 1² + 2² + 3² + … + N²= (N (N + 1) (2n + 1)) / 6 .[Here N=5]

So, SumSqN= 1²+ 2²+3²+4²+5² = 55.

And, let the sum of the squares of all the array elements be SumSq.

SumSq= 1²+2²+2²+3²+4²=34.

Now,

SumSq = SumSqN + A² - B²

SumSq - SumSqN = (A + B) (A - B)

So, 34–55= (A + B) (A - B) → -21=(A + B) (A - B) → Equation 2.

Put value of (A - B) from equation 1 in equation 2,

-21=(A + B) (A - B) → -21=(A+B)(-3)

A + B = -21 / (-3) = 7 →(Equation 3)

Solving equation 1 and equation 3 will give,

B = (((SumSq - SumSqN) / (Sum - SumN)) + SumN - Sum) / 2

And, A = Sum - SumN + B.

B= (((34–55)/(12–15))+15–12)/2 =5 [Missing value]

A= 12–15+5= 2 [Repeating Value]

Now, we will execute this through python coding.

This above approach will take no extra space only having time complexity (Linear)in O(n).

Linear Time Complexity - O(n)