<p>Given an integer array <code>nums</code> where&nbsp;every element appears <strong>three times</strong> except for one, which appears <strong>exactly once</strong>. <em>Find the single element and return it</em>.</p>

<p>You must&nbsp;implement a solution with a linear runtime complexity and use&nbsp;only constant&nbsp;extra space.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [2,2,3,2]
<strong>Output:</strong> 3
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [0,1,0,1,0,1,99]
<strong>Output:</strong> 99
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li>Each element in <code>nums</code> appears exactly <strong>three times</strong> except for one element which appears <strong>once</strong>.</li>
</ul>

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        long long aux = 1;
        for (int i = 0; i < 20; i++) aux *= 3;
        const long long MOD = aux;

        vector<int> ans(21, 0);
        for (long long num : nums) {
            if (num < 0) {
                num = MOD - num;
            }
            for (int i = 0; i < 21; i++) {
                ans[i] = (ans[i] + (num % 3)) % 3;
                num /= 3;
            }
        }

        long long num = 0;
        long long p = 1;
        //for (auto i : ans) cout << i << " ";
        //cout << endl;
        for (auto it = ans.begin(); it != ans.end(); it++) {
            //cout << num << endl;
            num += p * (*it);
            p *= 3;
        }

        if (ans.back() > 0) {
            //cout << "Entrou" << endl;
            //cout << num << endl;
            num -= MOD;
            num *= -1;
            //cout << num << endl;
        }      

        return num;
    }
};
12100