I forgot to mention what exact number we need to add to get all numbers from 1 to N.
Solution is, no matter what set of numbers are given, we will need to add missing numbers from (1,2,4,8,16,32,64....so on) which is nothing but power of 2.
Use LinkedList and HashMap, map is needed to keep the track of node in linkedlist.
1. Create -> add node to both linkedlist and map O(1)
2. Retrieve -> get the reference of the node in list using map and return the node. O(1)
3. Update -> get the reference of the node in list using map and update it in the list O(1)
4. Delete -> get the reference of the node in list using map and delete it from the both linkedlist and map O(1)
My previous below solution gives only number of elements needed without even traversing the array.
Minimum floor(Log(N))+1 elements will be needed to make all 1 to N numbers using ADD operation.
2^0 = 1 (if N<=1 then required number of elements is 0+1 = 1)
2^1 = 2 (if N>=2 & N<=3 then required number of elements is 1+1 = 2)
2^2 = 4 (if N>=4 & N<=7 then required number of elements is 2+1 = 3)
2^3 = 8 (if N>=8 & N<=15 then required number of elements is 3+1 = 4)
2^4 = 16 (if N>=16 & N<=31 then required number of elements is 3+1 = 4)
Here is solution what numbers need to be added to the array.
1. add 1 at index 0 in solutionArray
2. if 1 is already there in inputArray then just increment the index of inputArray.
3. loop while solutionArray[solutionIndex]*2 < N
4. check if next element in inputArray is less than current solutionIndex value * 2.
if(true) then copy the element from inputArray
else add solutionIndex value * 2 in the solution array.
- Naveen August 09, 2015