Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
import java.util.*; public class Solution { public int singleNumber(int[] A) { // Note: The Solution object is instantiated only once and is reused by each test case. Hashtable<Integer, Integer> table = new Hashtable<Integer,Integer>(); for(int i =0 ; i < A.length ; i++){ if(table.containsKey(A[i])){ table.put(A[i],table.get(A[i])+1); } else{ table.put(A[i],1); } } for(int i = 0 ; i < A.length ; i++){ if(table.get(A[i]) !=3) return A[i]; } return -1; } }