136. Single Number Leetcode Solution
Single Number Leetcode Problem :
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 :
Input: nums = [2,2,1]
Output: 1
Single Number Leetcode Solution :
Constraints :
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element in the array appears twice except for one element which appears only once.
Example 1:
- Input: nums = [4,1,2,1,2]
- Output: 4
Example 2:
- Input: nums = [1]
- Output: 1
Intution :
We can do this using unordered_map as we need to count the frequency of element.
Approach :
- Make an unordered map in which store the count of all values present in an array.
- Traverse through map and check which value has count 1 and then break through loop and store that value in ans variable.
- Return ans.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
int singleNumber(vector< int>& nums) {
int ans;
unordered_map< int,int>um;
for(int i=0;i< nums.size();i++){
um[nums[i]]++;
}
for(auto x:um){
if(x.second==1){
ans=x.first;
break;
}
}
return ans;
}
};Java
class Solution {
public int singleNumber(int[] nums)
{
Map< Integer,Integer> map=new HashMap< Integer,Integer>();
for(int i=0;i< nums.length;i++)
{
if(map.containsKey(nums[i]))
map.replace(nums[i],map.get(nums[i]),map.get(nums[i])+1);
else
map.put(nums[i],1);
}
for(int i=0;i< nums.length;i++)
{
if(map.get(nums[i])==1)
return nums[i];
}
return 0;
}
}
Python
from collections import defaultdict
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# space of hash map is O(1) which is 0-9 = 10
n_hash = defaultdict(int)
for val in nums:
n_hash[val] += 1
for val in n_hash:
if n_hash[val] == 1:
return val
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment