Blogs   

Two Integers Occurring Odd Number Of Times

Published on 29 Jul 2025  ·  Written by Aditya Mayukh Som

Problem Link

from typing import *

def twoOddNum(arr: List[int]) -> List[int]:
    # XOR all the numbers
    xor: int = 0
    for num in arr:
        xor ^= num

    # Now xor is the xor of two odd occuring numbers, x1 and x2
    # We observe that one of the bit which is set in xor, must be
    # different in x1 and x2 as same bits xor becomes zero, diff
    # bits xor will become one, hence we find the least significant
    # set bit from the xor, using n & (~n + 1) method, which is
    # equivalent to xor & -xor.
    mask = xor & -xor

    # now we can partition arr into two groups, for one, the and with
    # mask will be zero as the bit is unset, for the other, and with
    # mask will be non zero as the bit is set (1 & 1 = 1). So that
    # will seperate the two odd occuring numbers into separate groups
    # and the xor of the individual group will cancel all even occuring
    # numbers, hence xor of the two seperate groups will give us the two
    # odd occuring numbers

    n1: int = 0
    n2: int = 0
    for num in arr:
        if num & mask == 0:
            n1 ^= num
        else:
            n2 ^= num

    res = [n1, n2]
    res.sort(reverse = True)
    return res
Written by Aditya Mayukh Som.