Input:
Array of n integers, containing numbers in the range [1,n].
Each integer appears once except A which repeats twice and B which is missing.
Output:
Return A and B.
Example:
Input:[3 1 2 5 3]
Output:[3, 4]
A = 3, B = 4
My approach:
public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public ArrayList<Integer> repeatedNumber(final List<Integer> A) {
//O(n) solution
//Store the count of all the numbers appearing in the list
int [] count = new int[A.size()];
int rep_num = 0,miss = 0;
//Increase the count at the index location
for( int i = 0; i < A.size(); i++ )
{
int ind = A.get(i);
count[ind - 1]++;
//
if(count[ind - 1] == 2)
{
rep_num = ind;
break;
}
}
//If the count has not been updated, then the number is missing in the array
for(int i = 0; i < count.length; i++ )
{
if(count[i] == 0)
miss = i+1;
}
ArrayList<Integer> num = new ArrayList<Integer>();
num.add(rep_num);
num.add(miss);
return num;
}
}
I have the following questions:
How can I further optimize my code?
Is there any better way to solve this question (i.e. using a better data structure, lesser lines of code)?
Question asked on: interviewbit.com