Skip to main content
Talentd

Once Twice - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBit Manipulation3 min read
Practice this problem

Problem Statement

You are given an integer array nums. In this array:

  • Exactly one element appears once.

  • Exactly one element appears twice.

  • All other elements appear exactly three times.

Return an integer array of length 2, where the first element is the one that appears once, and the second is the one that appears twice.

Your solution must run in O(n) time and O(1) space.

 

Example 1:

Input: nums = [2,2,3,2,5,5,5,7,7]

Output: [3,7]

Explanation:

The element 3 appears once, and the element 7 appears twice. The remaining elements each appear three times.

Example 2:

Input: nums = [4,4,6,4,9,9,9,6,8]

Output: [8,6]

Explanation:

The element 8 appears once, and the element 6 appears twice. The remaining elements each appear three times.

 

Constraints:

  • 3 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • nums.length is a multiple of 3.
  • Exactly one element appears once, one element appears twice, and all other elements appear three times.

Approach Overview

Problem Overview: You are given an integer array where every value appears exactly twice except one value that appears only once. Return the element that occurs once. The challenge is to do it efficiently without extra memory.

Approach 1: Hash Map Frequency Count (O(n) time, O(n) space)

The straightforward solution counts how many times each number appears. Iterate through the array and store frequencies in a hash map. After building the map, scan through the entries and return the number with frequency 1. This approach is easy to implement and works for any frequency‑based problem, but it uses additional memory proportional to the array size.

Approach 2: Sorting the Array (O(n log n) time, O(1) extra space)

Another option is sorting the array first. Once sorted, identical values become adjacent. Iterate through the array in pairs: if nums[i] != nums[i+1], the current element is the one that appears once. If they match, skip both and continue. Sorting simplifies comparison logic but increases runtime to O(n log n). This approach works when modifying the array is acceptable.

Approach 3: Bit Manipulation with XOR (O(n) time, O(1) space)

The optimal solution relies on the XOR operation. XOR has two useful properties: a ^ a = 0 and a ^ 0 = a. If you XOR all elements in the array, every pair cancels itself out because identical numbers XOR to zero. Only the number that appears once remains in the final result. Iterate through the array and keep a running XOR value. The final accumulator is the answer.

This technique is common in problems involving duplicate cancellation and shows up frequently in bit manipulation interviews. It also works well with linear scans over an array, making it both memory‑efficient and fast.

Recommended for interviews: The XOR solution is what interviewers usually expect. It demonstrates understanding of bit operations and achieves optimal O(n) time with O(1) space. Starting with the hash map approach shows you understand the problem, but moving to the XOR optimization signals stronger problem‑solving skills and familiarity with bit manipulation patterns.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map Frequency CountO(n)O(n)General solution when memory usage is not a concern and simplicity is preferred
SortingO(n log n)O(1)When modifying the array is allowed and you want a simple comparison-based approach
Bit Manipulation (XOR)O(n)O(1)Optimal approach for large arrays and interview settings

Frequently Asked Questions

Is Once Twice easy or hard?
The problem is typically classified as Medium because recognizing the XOR trick requires familiarity with bit manipulation patterns. The brute-force or hash map approach is straightforward, but identifying the constant-space XOR solution demonstrates deeper algorithmic insight.
Once Twice Python/Java solution
Most implementations use a simple loop with XOR. Initialize a variable result = 0, then iterate through the array and compute result ^= num for each element. The final value of result is the number that appears once. The same logic works in Python, Java, C++, and Go.
How to solve Once Twice in O(n)?
Iterate through the array and keep a running XOR of all numbers. Because XOR removes pairs of identical numbers, duplicates cancel out automatically. After processing the entire array, the remaining value in the accumulator is the number that appears once. This approach achieves O(n) time and constant space.
What is the best approach for Once Twice?
The XOR-based bit manipulation approach is the most efficient. XOR cancels out duplicate numbers because a ^ a = 0 and a ^ 0 = a. By XORing every element in the array, all duplicated values disappear and the number appearing once remains. This runs in O(n) time with O(1) extra space.
Is Once Twice asked at Google/Amazon/Meta?
Frequency and XOR-based array problems are common in interviews at companies like Google, Amazon, and Meta. Variants such as Single Number and Single Number II frequently appear in coding interviews because they test understanding of bit manipulation and algorithmic optimization.
What data structure is used in Once Twice?
The optimal approach primarily uses bit manipulation with the XOR operator and does not require additional data structures. A hash map can also be used to count frequencies, but that increases memory usage to O(n).
What is the time complexity of Once Twice?
The optimal solution runs in O(n) time because the array is scanned once while applying the XOR operation. Space complexity is O(1) since only a single accumulator variable is used. Alternative methods like sorting take O(n log n) time, while hash map counting uses O(n) space.

Ready to solve this problem?

Practice Once Twice with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays