loading...

JAVA: CODING PROBLEM: FIND SINGLE NUMBER

inspire99 profile image Ganesh Swamypillai Originally published at gansai.blogspot.com ・3 min read

Thank you for πŸ“– , I πŸ™ invite you to my blog at this πŸ”—: https://gansai.blogspot.com/2020/04/java-coding-find-single-number.html

Problem:

Given an array, all elements appear twice, except one element.

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

Solution:

There are many approaches to solve this problem.

  1. Try to solve this, without scrolling down, on your own.
  2. Give yourself some time to think of solution. Keep a timer.
  3. Come back after some time, if you have a solution / pseudocode, you can comment it right away. Otherwise, no problem, you will eventually be able to solve such problems.

If you are interested in the approaches, you can scroll below.

The common bruteforce approach is to : Iterate over array and check with remaining elements if a duplicate is found, if not found, then that is the answer. But, while solving problems, it is not just about solving. It is also about thinking of trying to solve in different ways and also trying to solve it efficiently. ( Using less time and less space ). What is time complexity of this brute force approach? Basically we will be iterating the array twice.

So, Alt Text is the complexity.

But, can we do better?

Here are 4 approaches listed in below image.

SOLUTION

APPROACH 1: Using List



package com.technoparadigms.singlenumber;

import java.util.ArrayList;

public class SingleNumberList{


    public static void main(String[] args) {
        int array[] = {4,1,2,1,2};
        int singleNumber = findSingleNumber(array);
        System.out.println("The single number is "+singleNumber);
    }

    private static int findSingleNumber(int[] array) {

        ArrayList<Integer> numberList = new ArrayList<Integer>();

        for(int i: array){
            if(numberList.contains(i)){
                numberList.remove(new Integer(i));
            }
            else{
                numberList.add(i);
            }
        }

        return numberList.get(0);


    }
}

APPROACH 2: Using HashMap

Notice the usage of getOrDefault() method in HashMap. This is introduced in Java 8, very useful. Many of the programmers will agree with boilerplate code, where it involves couple of if-else statements to update hashmap entry. This is a single line statement to avoid boilerplate-code. very useful. read the java documentation again. you will appreciate this api.


package com.technoparadigms.singlenumber;

import java.util.HashMap;

public class SingleNumberHashMap{


    public static void main(String[] args) {
        int array[] = {4,1,2,1,2};
        int singleNumber = findSingleNumber(array);
        System.out.println("The single number is "+singleNumber);
    }

    private static int findSingleNumber(int[] array) {

        HashMap<Integer,Integer> singleNumberHashMap = new HashMap<Integer,Integer>();
        for(int i: array){
            singleNumberHashMap.put(i,singleNumberHashMap.getOrDefault(i, 0) + 1);
        }

        for(int i: array){
            if(singleNumberHashMap.get(i) == 1){
                return i;
            }
        }

        return 0;

    }
}

APPROACH 3: Using Math formula ( we can employ HashSet for the unique elements )



package com.technoparadigms.singlenumber;

import java.util.HashSet;

public class SingleNumberMath{

    public static void main(String[] args) {
        int array[] = {4,1,2,1,2};
        int singleNumber = findSingleNumber(array);
        System.out.println("The single number is "+singleNumber);
    }

    private static int findSingleNumber(int[] array) {
        HashSet<Integer> singleNumberHashSet = new HashSet<Integer>();

        int hashSetSum = 0;
        int arraySum = 0;
        int singleNumber = 0;

        for(int i: array){

            arraySum += i;
            if(singleNumberHashSet.add(i)){
                hashSetSum+=i;
            }
        }

        singleNumber = 2*hashSetSum - arraySum;
        return singleNumber;
    }
}

APPROACH 4: Using BIT MANIPULATION ( using XOR - ^ )

package com.technoparadigms.singlenumber;

public class SingleNumberBitXOR{


    public static void main(String[] args) {
        int array[] = {4,1,2,1,2};
        int singleNumber = findSingleNumber(array);
        System.out.println("The single number is "+singleNumber);
    }

    private static int findSingleNumber(int[] array) {
        int xorResult = 0; // start with 0

        for(int i: array){
            xorResult = xorResult ^ i;
        }

        return xorResult;
    }
}

πŸ–, πŸ™ for πŸ“–, you can Buy Me A Coffee

Posted on by:

Discussion

pic
Editor guide
 

First awesome visualization! I have one doubt though, for brute force approach, if we remove an element, won't it take O(n) extra time to rearrange the rest of the elements?

Awesome job explaining it well!

 

Yes, you are right, infact, when remove() is invoked, internally System.arrayCopy() (which handles the rearrangement) is invoked which is a native method. And time complexity of this method is O(n) - stackoverflow.com/questions/716559...