70: Find duplicate number

Given an array of integers, the array contains only one duplicate value. Return the duplicate value

Note: solution should use O(1) space

 

Example 1

Input:   [4, 3, 9, 15, 3]

Output:  3

Example 2

Input:   [3, 2, 4, 2]

Output:  2