✅ [Java] EASY Intuitive Sol | Full Explanation | 100% Faster | Bit Manipulation | Binary Search
Hello everyone, I hope you all are doing great.\nNote: If you found this post helpful then please do upvote!\n\nIn this post i\'ll explain 4 approach from worst
Hello everyone, I hope you all are doing great.\n**Note: If you found this post helpful then please do upvote!**\n\nIn this post i\'ll explain 4 approach from worst to best time complexity, and i\'ll also i\'ll try to explain the intution behind this.\nBefore we proceed to various approaches let\'s keep this thing in mind.\nAs You can see in the image below all the second element in the pair before the target or ans index is at odd index and after the target they shifted to one index and are at even indexes.\n![image](https://assets.leetcode.com/users/images/35047cf4-8b40-4ff2-99a4-53bf6d2a6904_1637394383.7849278.png)\n\n___\n**Approach 1 : Linear Search  - TC O(n) - SC O(1)**\n\nIn this approach we simply traverse through every pair from the nums array and keep checking if the current element is equal to the prev one, if not we will simply return the prev element. \n\n```\nclass Solution {\n    public int singleNonDuplicate(int[] nums) {\n\t//traverse through arrau and check if prev is equal to curr ,if not return prev\n        for(int i=1;i<nums.length;i+=2){\n         if(nums[i]!=nums[i-1]){\n             return nums[i-1];\n         }   \n        }\n\t\t//if didn\'t find means last element is single, here\'s the example [1,1,2,2,3]\n        return nums[nums.length-1];\n    }\n}\n```\n**Time Complexity: O(n)\nSpace Complexity : O(1)**\n___\n\n**Approach 2 : Bit manupulation - TC O(n) - SC (1)**\nHere we use the fact that  performing **XOR** with two same numbers give us **zero** and doing XOR with zero and other number will give us that number itself.\nhere\'s the example \n2 - 0010\n2 - 0010\n3 - 0011\n\nSo 2^2^3 = 3\n\nSo we simply iterate through the loop and do XOR and the final ans will be the required ans\n```\nclass Solution {\n\tpublic int singleNonDuplicate(int[] nums) {\n\t\tint ans = 0;\n        for(int num:nums){\n            ans^=num;\n        }\n        return ans;\n\t}\n}\n```\n**Time Complexity: O(n)\nSpace Complexity : O(1)**\n___\n**Approach 3 : Bit Manupulation Improved - TC O(n) - SC O(1)**\n\nSince we already know that every odd index represent second element of the pair which means at every odd index the **XOR** value will be **zero**, and if we found a situation where XOR is not zero at odd index which means last element was single element and that is the ans.\nwith this approach we will not iterate every time till last index and we can return when we find odd one.\n\n```\nclass Solution {\n\tpublic int singleNonDuplicate(int[] nums) {\n\t\tint ans = 0;\n        int prev = 0;\n        for(int i=0;i<nums.length;i++){\n            prev=ans;\n            ans^=nums[i];\n            if((i&1)==1 && ans!=0){ //here we are checking if the index is odd and ans is not zero\n                return prev;\n            }\n        }\n        return ans;\n\t}\n}\n```\n**Time Complexity: O(n)\nSpace Complexity : O(1)**\n___\n\n**Approach 4 : Binary Search - TC O(logn) - SC O(1)**\nSince the array is already sorted we can apply binary search to find the single element.\nBefore proceeding to this solution recall the above rule that i\'ve explained with the image.\n\n```\nclass Solution {\n    public int singleNonDuplicate(int[] nums) {\n        //the idea is to find mid element and if mid is single return it\n        //else mid is first element of the pair and \n            //is at even pos means ans will be to it\'s right\n            //else ans will be it\'s left\n        //else mid is second element and \n            //is at odd pos means ans will be towards right\n        //else ans will be towards left\n        \n        if(nums.length==1){\n            return nums[0];\n        }\n        \n        int lo = 0,hi = nums.length-1;\n        while(lo<=hi){\n            int mid = lo +(hi-lo)/2;\n            \n            \n            //means mid is second element of the pair\n            if(mid-1>=0 &&(nums[mid]==nums[mid-1])){ \n                //check if mid is at odd pos\n                if((mid&1)==1){\n                    lo = mid+1;\n                }else{\n                    hi = mid;\n                }\n                \n            }else if(mid+1<nums.length &&(nums[mid]==nums[mid+1])){ //means mid is first element of the pair\n                //check if mid is at even pos\n                if((mid&1)==0){\n                    lo = mid+2;\n                }else{\n                    hi = mid;\n                }\n                \n            }else{ //means mid is single\n                return nums[mid];\n            }\n        }\n        return -1;\n    }\n}\n```\n\n**Time Complexity: O(logn)\nSpace Complexity : O(1)**\n\n\uD83D\uDCCC  **Please Upvote \u2705 if you found this post useful for you!**
['Bit Manipulation', 'Binary Tree', 'Java']