279. Lone Among Triples
A warehouse scanner logs one tag ID per scan. Every tag was scanned exactly three times, except for a single stray tag that was scanned only once. The IDs are arbitrary 32-bit signed integers, so negative values occur, and the log is in no particular order.
Given the array nums, return the ID of the stray tag. The array is guaranteed to contain exactly one value that appears once, and every other value appears exactly three times, so its length is 3k + 1 for some k >= 0.
Counting every element against the whole array takes quadratic time, which is wasteful for long logs. Solve it in O(n) time with O(1) extra memory, without sorting and without a hash map.
Example 1
- Input:
- nums = [-4,9,9,-4,9,-4,17]
- Output:
- 17
- Explanation:
Every value except 17 appears three times; 17 appears once.
Example 2
- Input:
- nums = [2147483647,2147483647,-2147483648,2147483647]
- Output:
- -2147483648
- Explanation:
Every value except -2147483648 appears three times; -2147483648 appears once.
Example 3
- Input:
- nums = [-55,-55,0,-55,8,8,8]
- Output:
- 0
- Explanation:
Every value except 0 appears three times; 0 appears once.
Constraints
1 ≤ nums.length ≤ 4000, and nums.length = 3k + 1
-231 ≤ nums[i] ≤ 231 - 1
Exactly one value appears once; every other value appears exactly three times.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)