Biri Hariç Tüm Sayıların İkişer Adet Bulunduğu Dizideki Yanlız Sayıyı Bulma

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

>> Solution 1: Using list - O(n^2) time, O(n) space

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n^2) time, O(n) space
     *
     */
    public int singleNumber(int[] nums) {
       
        // O(n) space
        List<Integer> allElements = new ArrayList<>();
       
        // O(n^2) time
        for(int n : nums){
           
            Integer nWrapped = Integer.valueOf(n);
            if(allElements.contains(nWrapped)){
                allElements.remove(nWrapped);
            } else {
                allElements.add(nWrapped);
            }
           
        }
       
        return allElements.get(0);
    }

 Solution 2: Using hash map, O(n) time, O(n) space

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n) time, O(n) space
     *
     */
    public int singleNumber(int[] nums) {
       
        Map<Integer, Integer> elementCounts = new HashMap<>();
       
        // O(n) time, O(n) space
        for(int n : nums){
            Integer wrappedVal = Integer.valueOf(n);
            int currentCount = elementCounts.getOrDefault(wrappedVal,0)+1;
            elementCounts.put( wrappedVal , currentCount );
        }
       
        // O(n) time, O(1) space
        for(int n : nums) {
            Integer wrappedVal = Integer.valueOf(n);
            if(elementCounts.get(wrappedVal) == 1) {
                return n;
            }
        }
       
        throw new UnsupportedOperationException("Not a correct input set");
    }

 Solution 3a: Using math, O(n) time, O(n) space

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n) time, O(n) space
     *
     *  sumOfSet = a+b+c
     *  sumOfNums = c + 2*(a+b+c)
     *  sumOfNums = c + 2*sumOfSet - c
     *  c = 2*sumOfSet - c
    */
    public int singleNumber(int[] nums) {

        // O(n) time, O(1) space
        int sumOfNums = IntStream
            .of(nums)
            .sum();
       
        // O(n) time, O(n) space
        int sumOfSet = IntStream.of(nums)
            .boxed()
            .collect(Collectors.toSet())
            .stream()
            .mapToInt(Integer::intValue)
            .sum();
       
        return 2*sumOfSet - sumOfNums;
    }

  Solution 3b: Using math, O(n) time, O(n) space - but better runtime

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n) time, O(n) space
     *
     *  sumOfSet = a+b+c
     *  sumOfNums = c + 2*(a+b+c)
     *  sumOfNums = c + 2*sumOfSet - c
     *  c = 2*sumOfSet - c
    */
    public int singleNumber(int[] nums) {

        int sumOfNums = 0;
        int sumOfSet = 0;
        Set<Integer> elements = new HashSet<>(); // O(1) space
      
        // O(n) time
        for(int n : nums) {
            Integer intWrapped = Integer.valueOf(n);
            if(!elements.contains(intWrapped)) {
                elements.add(intWrapped);
                sumOfSet += n;
            }
            sumOfNums += n;
        }
      
        return 2*sumOfSet - sumOfNums;
    }

 

 Solution 4 : Bit operations, O(n) time, O(1) space

   /**
    * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
    *
    * Performance: O(n) time, O(1) space
    *
    *  a XOR 0 = n
    *  a XOR a = 0
    *  a XOR b XOR a = a
    */
    public int singleNumber(int[] nums) {

        // O(1) space
        int result = 0;
      
        // O(n) time
        for(int n : nums) {
            result = result ^ n;
        }
      
        return result;
    }