Lets Code Everyday - Day3

I was afraid when I wished for doing LeetCode every day because I know very well that I am not a consistent player. But I wanted to break that illusion about myself, Even on day three, I was concerned about whether I would be able to complete the goal I set for myself. Despite my fears and boundaries, I managed to answer one question and learn a lot today.

Question - 3 :-

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1

First approach:

class Solution {
    public int singleNumber(int[] nums) {
        List<Integer> newNums=new ArrayList<>();
        for(Integer n:nums) {
            newNums.add(n);
        }
        for(Integer i:newNums){
            int a=0;
            for(Integer j: newNums){
               if(Objects.equals(i,j)){
                  a++;
               }
            }
            if(a==1)
                return i;
        }
        return 0;
    }
}

Here is a step-by-step explanation of the code:

1. The code is trying to find a single number in an array of integers that appears only once.

2. It creates a new ArrayList called newNums to store the integers from the original array nums.

3. For each integer n in the nums array, it adds the integer to the newNums list using the add() method.

4. The code then loops over each integer i in the newNums list.

5. For each i, it initializes a counter a to 0.

6. It then loops over the newNums list again to compare the current i with every other integer j in the list.

7. If i is equal to j, it increments the counter a.

8. After comparing i with every other integer in the list, if a is equal to 1, it means that i appears only once in the list.

9. If i appears only once in the list, it is returned as the answer.

10. If none of the integers in the list appear only once, the code returns 0 as the answer.

Note that this approach has a time complexity of O(n^2), which means it can become very slow as the size of the array increases.

Even I was surprised that I had created another list just to use for each loop, maybe because my brain is working on the outcome rather than senseful outcome 😂. I later realized and changed the approach, which is shown below.

Second approach:

class Solution {
    public int singleNumber(int[] nums) {
        for(int i:nums) {
            int a=0;
            for(int j: nums) {
               if(i==j)
                  a++;
            }
            if(a==1)
                return i;
        }
        return 0;
    }
}

Step by Step explanation for the above code

1. The function takes an integer array called nums as an input parameter and returns an integer.

2. The function loops through each integer i in the nums array.

3. For each integer i, a variable a is initialized to 0.

4. The function then loops through each integer j in the nums array again.

5. If the integer i is equal to the integer j, the variable a is incremented by 1.

6. After the inner loop completes, if the value of a is 1, it means that the integer i occurs only once in the nums array.

7. The function then returns the integer i.

8. If no integer occurs only once in the nums array, the function returns 0.

9. The time complexity of this code is O(n^2).

Third approach:

class Solution {
    public int singleNumber(int[] nums) {
     Set<Integer> set= new HashSet<>();
     for(int num:nums){
         if(!set.contains(num))
             set.add(num);
         else
             set.remove(num);
     }
      return set.iterator().next(); 
    }
}

1. Create a new HashSet object named "set" to store unique integers.

2. Iterate through each integer "num" in the input integer array "nums".

3. If the integer "num" is not already present in the HashSet "set", add it to the set using the "add" method.

4. If the integer "num" is already present in the HashSet "set", remove it from the set using the "remove" method. This ensures that only unique integers remain in the set.

5. After iterating through all the integers in the array "nums", the set should contain only one element, which is the single number that occurs only once.

6. Return the single number by getting the iterator of the set and returning its next element using the "next" method.

7. The time complexity of this approach is O(n) (Finally Senseful approach at least in my sense😁)