✔️ [C++] Easy and Concise O(logn) Solution (W/ Explanation)
Hello everyone, firstly thanks for refering to my solution in advance :)\n\nAPPROACH : \n So, the array has all the elements repeating twice except for one elem
Hello everyone, firstly thanks for refering to my solution in advance :)\n\n**APPROACH :** \n* So, the array has all the elements repeating twice except for one element which appears only once and the array is sorted. \n* This means that in every number that\'s repeated, the first number is at an even index (index%2==0) and the 2nd number is at an odd index. \n* The idea is to peform a binary search over the entire array and find out if this pattern follows. If somewhere this pattern is broken, then we\'re going to know in which half of the array there is an element that appears only once. \n* We reduce the search space to that half an search again, until we\'re left with a single element, which is the final answer.\n\nLet us look at the first example : \n                 \n```\n        0    1    2    3    4    5    6    7    8\nnums = [1,   1,   2,   3,   3,   4,   4,   8,   8]\n\nWe start with left = 0, right = 8 => mid = 0+(8-0)/2 = 4\nNow, 4 is an even index which means the first repeating number should be at 4 and the next at 5. \nBut nums[4] != nums[5]. So on the left half the pattern\'s broken. \n\nNow, left = 0, right = 4 => mid = 0+(4-0)/2 = 2\nNow again 2 is an even number so nums[2] should be equal to nums[3], but it is not. \n\nSo again, left = 0, right = 2 => mid = 0+(2-0)/2 = 1\n1 is an odd number and nums[1] == nums[0]. So, we do l = mid+1 (Since the left half has the pattern). \n\nNow l = r = 2. \nHence stop the search and return nums[l] = 2.\n```\nLet us look at another example : \n                 \n```\n        0    1    2    3     4    5     6    \nnums = [3,   3,   7,   7,   10,   11,   11]\n\nWe start with left = 0, right = 6 => mid = 0+(6-0)/2 = 3\nNow, 3 is an odd index and nums[3] == nums[2]. So on the left half the pattern is followed. We move to the right half. \n\nNow, left = 4, right = 6 => mid = 4+(6-4)/2 = 5\nNow 5 is an odd number so nums[5] should be equal to nums[4], but it is not. \n\nSo now, left = 4, right = 5 => mid = 4+(5-4)/2 = 4\n4 is an even number but nums[4] != nums[5]. So, the pattern is not followed on the left side.\n\nNow l = r = 4. \nHence stop the search and return nums[l] = 10.\n```\n\n**Time Complexity :** O(logn); where n=length of the array\n**Space Complexity :** O(1) ; no extra space is required. \n\n**Code :**\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        if(nums.size()==1) return nums[0];\n        int l=0, r=nums.size()-1, mid, num;\n        \n        while(l < r){\n            mid = l+(r-l)/2;\n            num = (mid%2 == 0) ? mid+1 : mid-1;\n            if(nums[mid]==nums[num]) l = mid+1;\n            else r = mid;\n        }\n        return nums[l];\n    }\n\n};\n``` \n\nIf the question was to solve the problem in O(n) time complexity; we could use bit-manipulation.\n\n**Code :**\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int xOR=0;  //a^a = 0. So all the elements repeating twice become \'0\' and we return the non-repeating element.\n        for(int i=0;i<nums.size();i++) xOr ^= nums[i];\n        \n        return xOR;\n    }\n\n};\n```\nIf you like my solution and explanation, **please UPVOTE!**
['C', 'Binary Tree', 'C++']