We’ll go over all the methods, including brute force and the most efficient way to solve this problem.
we are going to solve one of the problems of Leetcode from by different approach.
Problem Statement
Given an integer array, exactly two elements appear only once, and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1,0]
Output: [-1,0]
Explanation of Problem Statement:
In this problem, an array list is given which contains the element, which there are only two elements that come for only one time, the other element comes more than two times, then we have to return the two elements which come single times in array List.
E.g., if nums=[1,2,1,3,2,5] here in the nums array list, each element comes more than one time except 3 and 5, so we have to return these two elements. The order of returning the element does not matter, as stated in the problem statement.
Output : [3,5] -> comes only one time in the array, so it is our answer.
Constraint :
Only Two elements in the List are coming single times, and others are repeated more than twice.
When the size of the array list is even, i.e., say N(6), then for the N-2(4) element, the N-2/2 element gets repeated at least two times, and the rest two elements come for a single time. E.g : [ 1, 2, 1, 2, 3, 4] here N=6 and N-2=4/2=2 element comes at least 2 times 1 and 2 , rest element
When the size of the array list is odd, i.e., say N(5), then at least one element comes more than two times to maintain Constraint 1. Of the question, the rest two-element comes from single times.
Above points 2 and 3 is a general understanding of the size of the array for N=6 and 5.
Solution:
1. Sorting Technique:
In this approach, we came up with a brute-force type approach to sort the element and iterate over the array’s length and check the previous and next element. If it matches that element, it is repeated, and we move forward to the next element. If the previous and next of the present element are not found to be the same, then it’s the singly occurring element in the list as an array is already sorted.
Algorithm for Sorting Technique:
Declare the size and Array of size say “N” and enter “N” element in it.
Element is entered following the Constraint of the question as only two elements are entered one time, rest are entered at least two times.
Sort the Array in ascending order or descending order as per your choice.
Now check the corner case at index “0” and “N-1” in separate conditions with the next and previous elements, respectively.
Now run a loop from index =1 to N-2, with a conditional statement of checking the i+1th and i-1th position element with present ith position element to verify more than one occurrence in the array list.
If a single occurrence is found, declare a size length of 2 Array as constraint tells only two elements to occur a single time in the array list.
At last completion of loop iteration over 1 to N-2, covering the lower and upper corner case of 1st and the previous element returns a temporary declare array containing single element occurrence in Array List.
publicclass singleNumber { staticint[] solution(int [] nums){ Arrays.sort(nums);// sorting the array int [] single_Element_In_Array=newint[2]; int j=0; if(nums[0]!=nums[1]){ single_Element_In_Array[j]=nums[0]; j++; } if(nums[nums.length-1]!=nums[nums.length-2]){ single_Element_In_Array[j]=nums[nums.length-1]; j++; } for(int i=1;i<=nums.length-2;i++){ if(nums[i]!=nums[i-1] && nums[i]!=nums[i+1]){ single_Element_In_Array[j]=nums[i]; j++; } } return single_Element_In_Array; } publicstaticvoidmain(String[] args){ Scanner sc=new Scanner(System.in); int size_of_array=sc.nextInt(); int [] nums=newint[size_of_array]; for(int i=0;i<nums.length;i++){ nums[i]=sc.nextInt(); } int [] single_element_in_array=solution(nums); for(int i=0;i<single_element_in_array.length;i++){ System.out.print(single_element_in_array[i]+" "); } } }
Input:
6
1 2 1 3 2 5
Output:
5 3
Time Complexity: O(N*log N), N* logN for sort array, N for iteration and comparison last, following, with the present element.
Space Complexity: O(1), as we are declaring an extra array of size two which constant time
2. HashMap Technique:
In this approach, we try to optimize the Time complexity from O(N*log(N)) to O(N) but to do so, our space complexity gets suffer as previous its O(constant), i.e., O(1) but using HashMap it becomes O(N) itself as for each element we are maintaining the frequency of every element.
Algorithm for HashMap Technique:
Declare the size and Array of size say “N” and enter “N” element in it.
Element is entered following the Constraint of the question as only two elements are entered one time, rest is entered at least two times.
Now declare a HashMap, which contains the frequency of each of the elements present in the Array.
Now iterate over the HashMap and check the KeySet value whose value is one. Then, store that element value in the array by overwriting it, so no extra space is created as already HashMap has taken N extra space.
After iteration over all the elements, assign the singly occurrence element array temporary declared of O(2) size, which usually takes O(1) Space in Constant Time.
Time Complexity: Time Complexity of the HashMap Technique is O(N).
Space Complexity: O(N) for HashMap and O(constant) for temporary arrays, which is generally O(N+constant) hence O(N). Also see, Euclid GCD Algorithm
Frequently Asked Question:
What is Sorting? Process of Arranging the element in Ascending or descending or specific order.
What is Time Complexity for sort the element? There are different types of sorting AlgorithmsSorting. Each has an additional TC. The list of some Algorithm is as follows
In this blog, we generally talked about the different approaches; one is Sorting. Another is HashMap to deal with the Two Singly element occur in Array list and try to do the solution in brute force manner sorting technique in O(N*log(N)) time complexity to optimize the solution in O(N) using HashMap.
If you feel confident, then why don’t you give it a try by submitting it here? Single Number III.
If you are a beginner in coding and want to learn DSA, you can look for our guided path for DSA, which is free!
39+ registered 