Start learning free

LESSON 400 OF 442 · BIT MANIPULATION

Single Number in Kotlin: O(1) Space with XOR

Practice O(n) Read the full explanation

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.


Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.
Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

What property can help identify a number that appears only once when all others appear twice?
Think about a bitwise operation that cancels out equal values.

XOR (^) has two key properties:
  • x ^ x = 0 — equal numbers cancel each other out
  • x ^ 0 = x — XOR with 0 leaves the number unchanged
If you XOR all elements in the array together, every duplicate pair cancels out to 0, leaving only the single number.
For example: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4

We iterate through the array once, so the Time Complexity is O(n).
We use only one extra variable, so the Extra Space is O(1).
STEP 1 OF 4
    Ctrl + Enter to check

    KOTLIN · BIT MANIPULATION

    Single Number in Kotlin, explained

    Problem overview

    singleNumber(nums) receives a non-empty IntArray in which every value appears exactly twice, except for one value that appears once. It returns that single value.

    For nums = [2, 2, 1] the answer is 1. For [4, 1, 2, 1, 2] it is 4, and for [1] it is 1. The array has up to 30,000 elements, and values range from -30,000 to 30,000, so negatives are possible. The lesson asks for O(n) time and O(1) extra space.

    Approach: XOR cancels pairs

    There are easy ways to find the odd one out. Sorting the array and looking for the element without a neighbour takes O(n log n). Counting with a hash map takes O(n) time but O(n) space. The space limit rules out the map, and the time limit rules out sorting.

    The solution uses the bitwise XOR operation. XOR compares two numbers bit by bit and gives 1 where the bits differ and 0 where they match. Three properties matter:

    • A number XOR itself is 0. Every bit matches, so 6 xor 6 is 0.
    • A number XOR 0 is the number. 6 xor 0 is 6.
    • Order and grouping don't matter. XOR is commutative and associative, so the numbers can be combined in any order.

    Now fold the entire array into one value with XOR. Because the order doesn't matter, you can imagine the equal pairs sitting next to each other. Each pair XORs to 0, and the zeros vanish into whatever is left. Only the single number has no partner, so it is the final value.

    Here is [4, 1, 2, 1, 2], starting from 0:

    1. 0 xor 4 is 4.
    2. 4 xor 1 is 5.
    3. 5 xor 2 is 7.
    4. 7 xor 1 is 6.
    5. 6 xor 2 is 4.

    The intermediate values look meaningless, but the end result is the single number, 4. The ones and twos have cancelled out, even though they were not next to each other.

    Step by step

    1. Start the accumulator at 0. var s = 0 is the running XOR. Zero is the neutral value, so the first number XOR-ed in is kept unchanged.
    2. Loop over the array. for (num in nums) visits every element.
    3. Fold each number in. s = s xor num updates the accumulator. A value seen the first time is added to it, and the second time it is cancelled out again.
    4. Return s. After the loop, only the value that was folded in an odd number of times is left, and that is the single one.

    The solution in Kotlin

    class Solution {
    fun singleNumber(nums: IntArray): Int {
        var s = 0
        for (num in nums) {
            s = s xor num
        }
        return s
    }
}

    Kotlin details worth a look:

    • xor is a named function. Kotlin has no ^ operator for bits. xor is an infix function on integer types, so s xor num is another way to write s.xor(num). Other bitwise helpers follow the same style: and, or, shl and shr.
    • Int is 32 bits. XOR works on every bit, including the sign bit, so negative numbers need no special handling. -5 xor -5 is 0, and the array [-5, 3, 3] returns -5. XOR also never overflows.
    • var. The accumulator changes in every pass, so it must be a var.
    • IntArray. The loop reads Int values straight from the array, with no boxing.
    • The single return is always reached. The loop has no early exit, so the function needs no fallback return. The constraints guarantee that the array is non-empty.

    Complexity

    Time: O(n). The loop makes one pass over the array, and each XOR takes constant time.

    Space: O(1). The function keeps a single integer, however large the array is. It doesn't modify the input.

    Edge cases and common mistakes

    • A single element. [1] gives 0 xor 1, which is 1.
    • The single value is 0. [7, 0, 7] returns 0. The function can't tell this result from "nothing found", but the constraints guarantee one single value exists, so nothing needs checking.
    • Negative values. [-7, 9, -7, 9, 0] gives 0, and [-5, 3, 3] gives -5, as shown above.
    • The single value is not first or last. The position doesn't matter, because the cancelling works in any order.
    • Using addition. Summing the array doesn't isolate the odd value; [2, 2, 1] sums to 5, not 1. The trick relies on x xor x being 0.
    • Applying it to other counts. The method works because each other value appears an even number of times, exactly two here. If values could appear three times, three copies of one value would not cancel, and XOR alone would give the wrong answer.

    Testing

    • [2, 2, 1] gives 1.
    • [4, 1, 2, 1, 2] gives 4.
    • [1] gives 1.
    • [-5, 3, 3] gives -5.
    • [-7, 9, -7, 9, 0] gives 0.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free