[LeetCode] Single Number II

Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it wi

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

考虑全部用二进制表示，如果我们把 第 ith 个位置上所有数字的和对3取余，那么只会有两个结果 0 或 1 (根据题意，3个0或3个1相加余数都为0). 因此取余的结果就是那个 “Single Number”。

LeetCode 306. Additive Number 累加数是一个字符串，组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 0 - 9 的字符串，编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。