algoadvance

Leetcode 3158. Find the XOR of Numbers Which Appear Twice

Problem Statement

Given an integer array nums where every element appears exactly twice except for one element which appears once, find the XOR of all elements that appear exactly twice.

Clarifying Questions

1. Q: Can we assume that the input array nums is non-empty? A: Yes, you can assume that the input array nums is non-empty.

2. Q: Should we consider the case where there are no numbers that appear exactly twice? A: No, the problem guarantees that every element appears exactly twice except for one element which appears once.

3. Q: Can the input array contain negative numbers? A: Yes, the input array can contain negative numbers as well as positive numbers.

Strategy

1. Using HashMap:
   • Use a HashMap to count the frequency of each element.
   • Iterate through the array and count occurrences of each number.
   • Then iterate through the HashMap to find elements with frequency exactly equal to 2.
   • XOR the elements which have the frequency equal to 2.

This method efficiently finds the numbers that appear twice and calculates their XOR.

Code

import java.util.HashMap;
import java.util.Map;

public class FindXOROfNumbersAppearTwice {

    public static int findXorOfDuplicates(int[] nums) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Count the frequency of each number
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        int result = 0;
        
        // Calculate the XOR for numbers that appear exactly twice
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() == 2) {
                result ^= entry.getKey();
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {4, 3, 7, 3, 7, 4, 8};
        System.out.println(findXorOfDuplicates(nums)); // Output should be 0 since 4 and 3 appear twice
    }
}

Time Complexity

• Time Complexity:
  • The time complexity is O(n) where n is the number of elements in nums. This is because we are making two passes through the array: one for counting the occurrences and another for finding the XOR of the elements appearing twice.
• Space Complexity:
  • The space complexity is O(n) in the worst case due to the extra space used by the HashMap to store the frequency of each element in the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?