Given an array of n elements, with all elements ranging from 1 to n except one is missing and one is duplicated; find the duplicate and missing element.

/*
     ALGORITHM
     ---------
     If we can get the duplicate element, missing elements can be found out by adding all the elements and subtracting from (n(n+1))/2 = sum of 1st n elements.
     Add the difference to duplicate element.
     1. Scan array from left to right.
                Pos =0 ; while pos < N
     2. Get value of current element and also its position if the array is in sorted order (desiredPos)
                which will be arr[pos]-1 (since array index begins with 0).
         a. If element is at its correct position
                If desiredPos == arr[pos-1] then move on to next element pos++.
         b. Else check value at desiredPos if it is correct then this is a case of duplicate element. Return duplicate value.
                Else if (arr[desiredPos] == arr[pos]) return arr[pos]
         c. Else swap arr[pos] and arr[desiredPos] and repeat step 2 .
   
     COMPLEXITY
     ----------
     Time  : O(n)
     Space : O(1)
   
*/

    int getDuplicate(int arr[],int size)
    {
        int pos = 0;
        while(pos <size)
        {
             int desiredPos = arr[pos]-1;
             if(pos == desiredPos)
             {
                 pos++;
             }
             else if(arr[desiredPos] == arr[pos])
                     return arr[pos];
             else
             {
                 swap(arr,pos,desiredPos);
             }
        }
        return -1;
    }

/*
    ALTERNATE METHOD
    ----------------
    Let the missing number be x and duplicate element be y.
   
    Sum of all elements = 1+…+n – x + y (y is duplicate and x is missing).
    Sum (constant) = (n(n+1))/2 –x + y
    Let constant C1 = sum and constant C2 = (n(n+1))/2.
    Y – x = C1-C2.
   
    Product of all elements =( 1……n *y )/x
    Product = (n! * y )/x
    Let constant C3 = product and constant C4 = n!.
   
    C3/C4 = y/x
    (C3 * x)/C4 = y.
   
    2 variables and 2 equations, Substitute value of y in 1st equation and solve for x and y.
   
   
    COMPLEXITY
    Time  : O(n)
    Space : O(1)
*/