Array Product

Q: Given an unsorted array of I of N integers, find an array O of N integers such that O[i] is the product of all integers in I except I[i]. Solve without using division.

Soln approach: 
1. Break the product into two parts as O[i] = (I[0] * I[1] * ... * I[i-1]) * (I[i+1] * ... * I[N-1])

2. Calculate first part by iterating over I from 0 to N-1
3. Multiply the values from step 2 with the second part by iterating over I from N-1 to 0

Java code to do this:

Duplicate & missing number

Q: In an unsorted array of first N natural numbers which has a duplicate number and a missing number, find the duplicate and missing numbers.

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Sum of N^2 numbers = n(n+1)(2n+1)/6

3. Since there are 2 unknowns we can create 2 equations using the above formulae to solve them

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Multiplication of N numbers / n! = Duplicate/Missing

3. Again we can solve for the 2 unknowns using the above formulae

Both the above approach assumes that N^2 or N! can be held in an int/double etc without overflow. In Java we can make use of BigInteger but there is another approach to solve the problem using bit operators.

Soln approach:

Let Ai be the ith element of the array, 0 <= i < n

Let Bi be i+1

1. Find Duplicate XOR Missing = X

    - XOR all Ai and Bi

2. Find which rightmost bit is 1 in X = Y

    - X & ~(X - 1)

3. Partition A and B such that A1 and B1 has Y set and A2 and B2 does not have Y set

    - Iterate and use & operator over Y and elements of A and B

4. XOR elements of A1 and B1 = VALUE1

5. XOR elements of A2 and B2 = VALUE2

6. If A1.length > B1.length then VALUE1 = Duplicate and VALUE2 = Missing

    else VALUE2 = Duplicate and VALUE1 = Missing