Missing And Repeating Numbers

public class Solution {

    public static int[] findMissingRepeatingNumbers(int []arr) {

        // Write your code here

         //     X -> repeating , Y -> missing (assume)

    //     Sn -> sum of first n numbers 

    //     S -> sum of all numbers

    //     S - Sn = X - Y = val1 

    //     Sn2 -> square of first n numbers

    //     S2 -> sum of sq of all numbers

    //     S2 - Sn2 = X2 - Y2

    //              = (X + Y)(X - Y)

    //     X + Y = (S2 - Sn2)/(X - Y) = val2

    //     X + Y = val2

    //   + X - Y = val1

    //     2X    = val2 + val1

    //     X = (val2 + val1)/2..... Y = val2 - X 

        int sn = 0,s = 0,sn2 = 0,s2 = 0,x,y,val1,val2;

        for(int i=1;i<=arr.length;i++){

            sn+=i;

            sn2+=(i*i);

        }

        for(int a:arr){

            s+=a;

            s2+=(a*a);

        }

        val1 = s - sn;

        val2 = (s2 - sn2)/val1;

        x = (val2 + val1)/2;

        y = val2 - x;

        int[] ans = new int[2];

        ans[0] = x;

        ans[1] = y;

        return ans;

    }

}

vector<int> findMissingRepeatingNumbers (vector<int>& arr) {
       int rep = 0;  // Variable to store the repeated element
       int n = arr.size();
       
       // First loop to find the repeated element
       for(int i = 0; i < n; i++) {
           if(arr[abs(arr[i]) - 1] < 0) // If the element is already negative
               rep = abs(arr[i]); // We found the repeated element
           else
               arr[abs(arr[i]) - 1] *= -1; // Mark the element as visited by making it negative
       }
       
       int mis = 0;  // Variable to store the missing element
   
       // Second loop to find the missing element
       for(int i = 0; i < n; i++) {
           if(arr[i] > 0) {  // If the element is positive, it means that index+1 is the missing number
               mis = i + 1;
               break;
           }
       }
       return {rep, mis};
   }

The problem is to find two specific numbers in an array of size n: one number that is missing (not present in the array) and one number that is repeating (appears twice). The array is supposed to contain all integers from 1 to n exactly once, but one number is missing, and another number appears twice.

Calculate the Expected Sum:

• The sum of the first n natural numbers is calculated using the formula sum = n * (n + 1) / 2.
• As we traverse the array, we subtract each element from this expected sum. After this step, the remaining value in sum will be missing number - repeating number.

Identify the Repeating Number:

• We sort the array to easily identify the repeating number. Sorting helps because if a number is repeated, it will appear consecutively.
• As we iterate through the sorted array, we check if any two consecutive elements are the same. If they are, we store this as the repeating number.

Calculate the Missing Number:

• Since sum now holds the difference between the missing and repeating numbers, adding the repeating number to sum gives us the missing number.

Return the Results:

• Finally, return the repeating number and the missing number as an array.

Time Complexity:

• Sorting the array takes O(n log n).
• The rest of the operations (calculating sum, finding the repeating number) take O(n).
• Hence, the overall time complexity is O(n log n).

Space Complexity:

• The algorithm uses a constant amount of extra space, i.e., O(1).

import java.util.*;
public class Solution {
    public static int[] findMissingRepeatingNumbers(int []a) {
        // Write your code here
        int n=a.length;
        int sum=(n*(n+1))/2;
        for(int i=0;i<n;i++)
        {
            sum=sum-a[i];
        }

        Arrays.sort(a);
        int temp=0;
        

            int count=1;
        for(int j=1;j<n;j++)
        {
            if(a[j-1]==a[j])
                {
                    count=2;
                }
                if(count==2)
                {
                   temp=a[j]; 
                   break;
                }
        }

int arr[]=new int[2];
arr[0]=temp;
arr[1]=(sum+temp);


        return arr;



    }
}

public static int[] findMissingRepeatingNumbers(int []a) {

        int n = a.length;

        long sn1 = (n*(n+1))/2;

        long sn2 = (n* (n+1)* (2*n+1))/6;

        long s1 = 0;

        long s2 = 0;

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

            s1 += a[i];

            s2 += (long)a[i] * (long)a[i];

        }

        long sum1 = s1 - sn1;

        long sum2 = (s2 - sn2)/sum1;

        long repeatingNo = (sum1 + sum2)/2;

        long missingNo = repeatingNo - sum1;

        return new int[]{(int)repeatingNo, (int)missingNo};

    }

#include <vector>

using namespace std;

vector<int> findMissingRepeatingNumbers(vector<int> a) {

    long long n = a.size();

    long long SN = (n * (n + 1)) / 2;

    long long S2N = (n * (n + 1) * (2 * n + 1)) / 6;

    long long S = 0, S2 = 0;

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

        S += a[i];

        S2 += (long long)a[i] * (long long)a[i];

    }

    long long val1 = S - SN;  

    long long val2 = S2 - S2N; 

    val2 = val2 / val1;  

    long long x = (val1 + val2) / 2;  

    long long y = x - val1;  

    return {(int)x, (int)y};  

}

vector<int> findMissingRepeatingNumbers(vector < int > a) {

    // Write your code here

    int n =a.size();

    int hash[n+1]={0};

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

        hash[a[i]]++;

    }

    int rep=-1;int mis=-1;

    for(int i=1;i<=n;i++){

        if(hash[i]==2)rep=i;

        else if (hash[i]==0)mis=i;

        if(rep!=-1&&mis!=-1)break;

    }

    return {rep,mis};

}

INTUITION

We are given an array of size N, containing 1 to N elements (inclusive), where one element repeats twice, while one number from 1 to N, remains missing. Our task is to find these two numbers.

• There are a number of ways, you can find the repeating number, via counting frequency or via element-by-element comparison. I used the former method for O(N) time complexity.
• Once we find the repeating element, we can turn its repeated occurrence to ‘0’, and calculate the array's sum. 
• Now, if we subtract this array sum from the natural sum of N numbers, this will definitely be equal to the missing number.

CODE

public class Solution {
    //helper method to calculate sum of an array
    public static int sumOfArray(int[] arr){
        int sum=0;
        for(int i:arr){
            sum+=i;
        }
        return sum;
    }
    public static int[] findMissingRepeatingNumbers(int []a) {
        // Write your code here
        //do counting sort to find repeating element.
        //note it, then turn it 0
        //calculate sum of the array, substract its size from it since n=a.length;
        //that is the missing number
        int p=0,q=0,n=a.length;
        int[] freq= new int[a.length+1];
        for(int i=0;i<a.length;i++){
            freq[a[i]]++;
            if(freq[a[i]]>1){
                p=a[i];
                a[i]=0;
                break;
            }
        }
        //found repeating element p, set the repeating element to 0
        //a[1,2,3,0]
        //now to find the missing, q -> sum of natural nums upto n - sum of arr
        q=(n*(n+1)/2)-sumOfArray(a);
        return new int[]{p,q};
    }
}

Hope you liked the solution.

vector<int> findMissingRepeatingNumbers(vector < int > a) {

    long long n=a.size();

    long long sum= (n*(n+1))/2;

    long long sqsum=(n*(n+1)*(2*n+1))/6;

     long long arrsum=0;

      long long arrsqsum=0;

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

       arrsum+=a[i];

       arrsqsum+=(long long)a[i]*(long long)a[i];

    }

    long long val1=arrsum-sum;//x-y

    long long val2=arrsqsum-sqsum;//(x-y)(x+y)

    val2=val2/val1;//x+y

    long long repeater=(val1+val2)/2;

    long long missing=repeater-val1;

    return {(int)repeater,(int)missing};  

}

vector<int> findMissingRepeatingNumbers(vector < int > a) {

    // Write your code here

    long long n = a.size();

    long long SN = (n * (n+1))/2;

    long long S2N = (n * (n+1) * (2*n+1))/6;

    long long s=0 , s2 =0;

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

        s += a[i];

        s2 += (long long)a[i] * (long long)a[i];

    }

    long long val1 = s-SN;

    long long val2 = s2-S2N;

    val2 = val2/val1;

    long long x = (val1 + val2)/2;

    long long y = x - val1;

    return {(int)x , (int)y};

}

vector<int> findMissingRepeatingNumbers(vector < int > a) {

    long long n = a.size();

    //moving with 2 formula's 

    // s - sn = x-y 

    //s2 -s2n

    long long sn = (n*(n+1))/2;

    long long s2n = (n*(n+1)*(2*n+1))/6;

    long long s=0, s2 = 0;

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

        s += a[i];

        s2 += (long long)a[i] * (long long)a[i];

    }

    long long val1 = s-sn; //x-y

    long long val2 = s2-s2n;

    val2 = val2/val1; //x+y

    long long x = (val1+ val2)/2;

    long long y = x-val1;

    return {(int)x, (int)y};

}