Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2] Output: 3
Example 2:
Input: [0,1,0,1,0,1,99] Output: 99
METHOD 1:
class Solution {
public int singleNumber(int[] nums) {
Arrays.sort(nums);
int i, length = nums.length, result=0;
for(i=0;i<length;){
if(i==length-1){
result = nums[i];
break;
}
else if(nums[i] == nums[i+1] && i+3<=length){
i+=3;
}
else{
result = nums[i];
break;
}
}
return result;
}
}In this method we are going to solve by sorting and then by normal iteration.
1) Sort the array using Arrays.sort().
2) Now start iteration till end of array. While doing iteration follow below steps..,
a) If current position is last position, then store value in result and exits from loop.
b)
If current element and next element are same, then increase i by 3
(also take care of ArrayIndexOutOfBoundException such that incremented i
value should not go beyond array length)
c) Else store result and exits from loop.
But this solution is not optimized and having runtime 2ms. Please check over next solution which is given below.
METHOD 2:
class Solution {
public int singleNumber(int[] nums) {
int ones = 0, twos = 0 ;
int length = nums.length;
int common;
for( int i=0; i< length; i++ )
{
twos = twos | (ones & nums[i]); //step 2
ones = ones ^ nums[i]; //step1
common = ~(ones & twos); //step 3
ones &= common; //step 3
twos &= common; //step3
}
return ones;
}
}In this method we are going to solve sing Bit Manipulation. Please sollow step number as mentioned in comment.
1) ones store first occurrence of a number.
2) twos store second occurrence of a number.
3) If a number is found again, then set ones, twos to 0 and again check for a new number.
4) Finally return ones which contains non-repeated number.
This solution has runtime of 0ms.
[Example]
{1,1,1,2}
After First Iteration -- 1
Second occurrence twos -- 0
First occurrence ones -- 1
After Second Iteration -- 1
Second occurrence twos -- 1
First occurrence ones -- 0After Third Iteration -- 1
Second occurrence twos -- 0
First occurrence ones -- 0After Fourth Iteration -- 2
Second occurrence twos -- 0
First occurrence ones -- 2Related Posts:
Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation
Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation
Click Follow button to receive updates from us instantly.
Please let us know about your views in comment section.
Comments
Post a Comment