Single Number with Follow-up

amazon Given a non-empty array of integers, every element appears twice except for one. Find that single one. Your algorithm should have a linear runtime complexity, and you should not use any extra space. Input: [2,2,1] Output: 1 Input: [4,1,2,1,2] Output: 4 Input: [1] Output: 1 Example Input [2,2,1]