Single Number II

• Create a HashMap<Integer, Integer> to store the frequency of each number.
• Iterate through the nums array. For each number num, increment its count in the map.
• After building the frequency map, iterate through its entries.
• Return the key for which the corresponding value (frequency) is 1.

The algorithm involves two main passes over the data. First, we iterate through the nums array to build a frequency map. For each number, we use it as a key and its frequency as the value. If the number is already in the map, we increment its value; otherwise, we add it with a value of 1. In the second pass, we iterate through the entries of the hash map. The entry whose value is 1 corresponds to the single number, and we return its key. This method is straightforward to implement and understand but does not meet the space complexity requirement of the problem.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int singleNumber(int[] nums) {6        Map<Integer, Integer> freqMap = new HashMap<>();7        for (int num : nums) {8            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);9        }10 11        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {12            if (entry.getValue() == 1) {13                return entry.getKey();14            }15        }16        // This line should not be reached given the problem constraints17        return -1;18    }19}

• Initialize a variable result to 0.
• Loop through each bit position i from 0 to 31.
• For each bit position, calculate the sum of the i-th bits of all numbers in the nums array.
• If the sum of bits for the i-th position is not a multiple of 3, it means the single number has a 1 at this bit position.
• Set the i-th bit in the result using a bitwise OR operation: result |= (1 << i).
• After checking all 32 bits, result will hold the single number.

We can determine the bits of the single number one by one. For each bit position from 0 to 31 (for a 32-bit integer), we calculate the sum of the bits of all numbers in the array at that specific position. Let's say for the i-th bit, the sum is S. If the i-th bit of the single number is 0, then all other numbers contribute to this sum. Since each of them appears three times, their i-th bits will be summed up in groups of three, making S a multiple of 3. However, if the i-th bit of the single number is 1, then S will be (a multiple of 3) + 1. Therefore, by checking S % 3, we can determine the i-th bit of the single number. We construct the final result by setting the bits accordingly.

1class Solution {2    public int singleNumber(int[] nums) {3        int result = 0;4        // Iterate over each bit position (0 to 31 for a 32-bit integer)5        for (int i = 0; i < 32; i++) {6            int sumOfBits = 0;7            // Calculate the sum of the i-th bit for all numbers8            for (int num : nums) {9                // Check if the i-th bit is set in the current number10                if (((num >> i) & 1) == 1) {11                    sumOfBits++;12                }13            }14            // If the sum is not a multiple of 3, the single number has a 1 at this bit position15            if (sumOfBits % 3 != 0) {16                // Set the i-th bit in the result17                result |= (1 << i);18            }19        }20        return result;21    }22}

• Initialize two integer variables, ones and twos, to 0.
• Iterate through each num in the input array nums.
• In each iteration, update ones and twos using the following bitwise formulas:
  • ones = (ones ^ num) & ~twos
  • twos = (twos ^ num) & ~ones
• After the loop completes, the ones variable will contain the single number that appeared only once.
• Return ones.

The idea is to track the count of '1's for each bit position modulo 3. We can represent these counts using two bits: (twos, ones). The state transitions are as follows:

• 00 -> 01 (seen once)
• 01 -> 10 (seen twice)
• 10 -> 00 (seen three times, reset) We iterate through the input array nums. For each number num, we update the ones and twos variables to reflect these state transitions for every bit. The update logic is:
• ones = (ones ^ num) & ~twos;
• twos = (twos ^ num) & ~ones; For bits belonging to the single number, they will transition to state 01 and remain there. For bits belonging to numbers that appear three times, they will cycle through 01, 10, and back to 00, effectively canceling themselves out. After processing all numbers, the ones variable will hold exactly the single number.

1class Solution {2    public int singleNumber(int[] nums) {3        int ones = 0;4        int twos = 0;5        for (int num : nums) {6            // 'ones' holds the bits that have appeared 3k+1 times7            // 'twos' holds the bits that have appeared 3k+2 times8            ones = (ones ^ num) & ~twos;9            twos = (twos ^ num) & ~ones;10        }11        return ones;12    }13}