Find Missing And Repeating | GFG | Time Complexity O(n)

Statement - Given an unsorted array Arr of size N of positive integers. One number 'A' from set {1, 2, …N} is missing and one number 'B' occurs twice in array. Find these two numbers.

Example 1:

Input:
N = 2
Arr[] = {2, 2}
Output: 2 1
Explanation: Repeating number is 2 and  

smallest positive missing number is 1. 

Problem Link - Click

Code - Time Complexity O(n), Space Complexity O(1).

class Solution{

        #define ll long long int

public:

    int *findTwoElement(int *arr, int n) {

        // code here

        ll n1 = (ll) n; 

        ll x = n1 * (n1 + 1) / 2;

        ll y = 0;  

        for(int i = 0; i < n; i++)

        {

            y += (ll) arr[i];

        }

        ll s = x - y;

        ll x_sq = n1 * (n1 + 1) * (2 * n1 + 1) / 6;

        ll y_sq = 0; 

        for(int i = 0; i < n; i++)

        {

            ll t = (ll) arr[i];            

            t = t * t;           

            y_sq += t;

        }

        

        ll s1 = x_sq - y_sq;        

        ll s_xy = s1 / s;        

        ll r = (s_xy + s) / 2;        

        ll missing = abs(s_xy - r);        

        int *ans = new int(2);        

        ans[0] = (int) missing;

        ans[1] = (int) r;

        

      return ans;        

    }

};

Offers For You