Single non-repeating element in an array (LeetCode 136) | Full solution with Examples

Single Number is a programming challenge on LeetCode. You are given an array of all positive integers. All the integers are repeated exactly twice except one. We need to find that number with a linear time complexity and using the minimum space possible. Watch the video to understand the problem in a simplified manner. I then work along with you to solve it first using a Brute Force approach, and then an efficient approach. All along with visuals and explanations.
00:00 - Intro
00:27 - Problem Statement and Test Case
01:26 - Method 1 (Brute Force)
03:17 - Method 2 (Using Map)
04:46 - Method 3 (Using XOR)
07:15 - Dry-run of code
📚 Links I talk about in the video:
Actual problem on LeetCode: leetcode.com/problems/single-...
Code on Github: github.com/nikoo28/java-solut...
Test cases on GitHub: github.com/nikoo28/java-solut...
📘 A text based explanation is available at: studyalgorithms.com/array/sin...
Further Reading:
Some low-level bit hacks you must know: studyalgorithms.com/theory/lo...
To see more videos like this, you can show your support on www.buymeacoffee.com/studyalg...
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
#leetcode #programming #tutorial

[@ploratran]

The XOR explanation is the best. I don't see this approach elsewhere. Thank you!

[@chetankharote9614]

This is exactly the type of explanation i needed. Good explanation

[@rodiermadiande249]

Thanks, I finally get it👌

[@mr.eleven2141]

int ans = 0 ;
Arrays.sort(nums);
for( int i = 0 ; i < nums.length ; i++){
if(i%2==0 ){
ans = ans + nums[i];
}else{
ans -= nums[i];
}
}
return ans;

[@takka6163]

sort uses n log n time bro

[@fathimaththasneemvv4012]

thank you ..its great explaination

[@Deepak-hv8uh]

This man is godly🤲💯

[@ishaanpareek5751]

best explanation

[@MVCS_Priya]

Best explanation and it's easy to understand

[@nikoo28]

Thanks for liking

[@unemployedcse3514]

awesome ❤

[@vamshisundupalle6141]

nice explanation

[@vanshikadubey13]

The best 🔥

[@user-to2wm5dk1w]

Thanks alot🎉🎉

[@subee128]

Thanks

[@atrikashow8118]

Thank you very much Sir

[@nikoo28]

All the best

[@HakunaMatata57046]

Approach was good but I don't know why GFG is not accepting this solution. 0/203 test cases were passed🙃

[@farjanashaik9601]

What if I want to return the first non-repeatable element using method 3

[@nikoo28]

As soon as you xor all the elements, you will get the non-repeating number in the result

[@chetangiradkar]

@Nikhil if you're still active, could you please shed light over a similar problem statement I have. The only change in my problem statement is that the repeating integers are paired contiguously and now it needs to be in O(log n). Couldn't figure out how I should go about solving it...

[@nikoo28]

Provide me a link

[@learning.byajit]

Here int sing =nums[0];
Means we have assing 0 in sing , after that when loop run fast time the , sing = sing^nums[i];
0^1 and sing store 1

[@ravi.m4954]

Hi Nikhil thanks for knowledge sharing.I have one question if my array contains odd number of duplicates like 3 times then xor output same number right .this case how to handle with xor?

[@nikoo28]

A XOR A = 0
0 XOR A = A

[@ravi.m4954]

@@nikoo28 thanks for reply.My question is if I use xor on input which non repeated element and duplicate element with 3 times occurence ex [a,b,b,b] in this xor will give both a and b right .but expected is only a since non duplicate. Can you tell me xor will work in this input scenario

[@rocktatnine]

How to solve this problem if all the repeating elements appear thrice and not twice. Ex : 19, 13, 13, 13 where Ans is 19.

[@accuracy4391]

but sir what if one more element in present in the array? and that element is 6 then there will be two elements left after Xor operation and that two elements will be 2 and 6. then how we choose the answer?

[@gunturrecipes951]

I think you should read the question carefully...only one element does not get repeated..

[@accuracy4391]

@@gunturrecipes951 yes sir i got it thankyou so much

[@nagalakshmi495]

What is the complexity of the method 3?

[@nikoo28]

The time complexity is O(n) as we are just doing one scan and space complexity is O(1) because we are not using any extra space.

[@karthik-varma-1579]

Nikhil sir Can You Prepare a excel sheet or atoz sheet so that we follow sequencily watching videos

[@nikoo28]

Yes, I am working on a roadmap. Meanwhile have you taken a look at the playlists? :)

[@karthik-varma-1579]

Yes Sir. I have seen Arrays as I am beginner I don't know what to watch next 🙄

[@alekseiap5949]

I dont' think that the methods 1 and 2 are applicable since in the problem statement it is mentioned that "You must implement a solution with a linear runtime complexity and use only constant extra space."

[@nikoo28]

yep...but for a new learner..it is important to understand a progressive approach :)

[@vamshisundupalle6141]

can you give code for brute force,it will help us a lot. please

[@nikoo28]

what problem are you facing when writing the code?

[@vamshisundupalle6141]

I don't know how to move the code after condition in inner loop

[@vamshisundupalle6141]

Along with optimized solution can you brute force solution ,it will help us lot

[@politesitsha9557]

public static int findSingleNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[i] == nums[j]) {
count++; // will return 2 for duplicates
}
}
if (count == 1) {
return nums[i];
}
}
return -1; // return -1 if no single number found (this should not occur for the given problem)
}

[@gokulakannan3664]

Can we solve the question by using below method...?
class Solution {
public int singleNumber(int[] nums) {
Mapmap=new HashMap();
for(int i=0;i

[@nikoo28]

Try to debug the code using some print statements and then you can understand the code flow.

[@gokulakannan3664]

@@nikoo28 It shows compilation error

[@politesitsha9557]

Variable res is declared inside the if statement's scope and you're trying to return it outside that scope.
int res = -1; // Initialize res to some default value, so that you return -1 if a single number is not found
// declare outside the Find the number with frequency 1 for loop

[@jorgericardosoares2790]

Is this the best solution for this problem, ins't?

[@nikoo28]

If we can think of a better solution, I am happy to discuss :)

[@jorgericardosoares2790]

​@@nikoo28 This solution has got 100% of perfomance on Codility plataform in a similar problem. I can't think of anything better haha. Congrats for the channel. I have subscribed it!

[@nikoo2805]

@@jorgericardosoares2790 glad to hear that