There are numbers from 1 to N in an array, out of these, one of the number gets duplicated and one is missing.
The task is to write a program to find out the duplicate number.
(example: 1 2 3 3 4 5)
Already Solved the question in your head ?? Take this.. : No using any auxiliary space like arrays.
For the first part: By adding up all the elements of the array and then comparing it with the value that from the formula for sum of 'n' numbers, you can find out the difference.
ReplyDeleteSecond more optimized solution : Use the XOR operator ' ^ '. Use this operator on all the elements of the array and your will be left with the duplicate number at the end. Why will this happen ?? Recall the truth table of XOR :)