Delivered instantly as a PDF via email. For Software Engineers & SDETs
150 programming interview questions and answers
5 proven approaches to crack algorithm questions
10 mistakes candidates make, and how to avoid them.
How to prepare for technical and behavioral questions without wasting your time!
"The BEST book for acing your interview. It helped me land my Microsoft job, and it was worth every penny!" - Ravi (Accepted at Microsoft, Amazon and Facebook)
30 Day Money Back Guarantee: Don't love the book? We'll give you your money back!More Info
Saturday, April 24, 2010
Missing number
Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.
One O(n) solution is to an array of size n, and initialize each element with 0. Loop over the input array, and increment the corresponding index in the other array. After this pass, the new array will have 2 elements with value 2, and two with value 0. Those are your repeated and missing numbers. This is of O(n) time and O(n) space, but requires 2 passes, one through the original array and then through the new array.
We can do it with just one pass using some algebraic manipulations.
Find the unique number. The logic for this would be after sorting, compare the element before and after, while iterating. IF a number is not equal to the number before and after it in the array after sorting, then that is the number that has occured only once
Sum of 1 to N no. n*(n+1)/2; Suppose x is repeating no and y is missing no. y-x= [Sum of 1 to n no.] – [Sum of Arrays no.] x/y=[product of arrays no.]/[product of 1 to n no.] Two equations and two variables can be calculated easily.
Ex: Array no={1, 2, 2, 3, 4}; y-x=5*(5+1)/2-12=15-12=3; y-x=3; x/y=[1*2*2*3*4]/[1*2*3*4*5]=2/5; x/y=2/5; x=(2/5)*y; y-(2/5)y=3; 5y-2y=15; 3y=15; y=5; x=2; Which can be calculated in order of n O(n); take the product and sum in single traversal and rest of the thing.
I create this function, it only use two variables: int FindDuplicate(int[] intArray) { int temp = 0; for (int i = 0; i < intArray.Length; i++) { if (intArray[i] == intArray[intArray[i] - 1]) { return intArray[i]; } else if( intArray[i]-1 !=i) { temp = intArray[intArray[i] - 1]; intArray[intArray[i] - 1] = intArray[i]; bool b = true; do { if (temp - 1 == i) { intArray[i] = temp; b = false; } else { if (temp == intArray[temp - 1]) { return temp; }
One O(n) solution is to an array of size n, and initialize each element with 0. Loop over the input array, and increment the corresponding index in the other array. After this pass, the new array will have 2 elements with value 2, and two with value 0. Those are your repeated and missing numbers. This is of O(n) time and O(n) space, but requires 2 passes, one through the original array and then through the new array.
ReplyDeleteWe can do it with just one pass using some algebraic manipulations.
What about using a linked list or a binary tree?
ReplyDeleteremove elements from the list/tree when they are found, then return the remaining number.
sort the array in increasing or decreasing order.
ReplyDeleteFind the unique number. The logic for this would be after sorting, compare the element before and after, while iterating. IF a number is not equal to the number before and after it in the array after sorting, then that is the number that has occured only once
question seems wrong/unclear
ReplyDelete(n(n+1)/2) - (sum of numbers in the array)
ReplyDeleteSum of 1 to N no. n*(n+1)/2;
ReplyDeleteSuppose x is repeating no and y is missing no.
y-x= [Sum of 1 to n no.] – [Sum of Arrays no.]
x/y=[product of arrays no.]/[product of 1 to n no.]
Two equations and two variables can be calculated easily.
Ex: Array no={1, 2, 2, 3, 4};
y-x=5*(5+1)/2-12=15-12=3;
y-x=3;
x/y=[1*2*2*3*4]/[1*2*3*4*5]=2/5;
x/y=2/5;
x=(2/5)*y;
y-(2/5)y=3;
5y-2y=15;
3y=15;
y=5;
x=2;
Which can be calculated in order of n O(n); take the product and sum in single traversal and rest of the thing.
If one number is repeating out of n numbers than find the sum of n-1 #'s which is =(n-1)*n/2.
ReplyDeletefor e.g Array No = {1,2,3,3,4}. where n = 5
Sum of 4 # = (n-1)*n/2 = 4*5/2 = 10
Sum of 5 # = (n)*(n+1)/2 = 5*6/2 = 15
Find the sum of the array using a for loop
which is 13.
now 13-10 = 3 which is repeating # and missing # is would be (Sum of 5 #)-(Sum of 4 #)=5.
The number could be {1, 5, 3, 4, 5}. In this case above solution will fail.
DeleteI create this function, it only use two variables:
ReplyDeleteint FindDuplicate(int[] intArray)
{
int temp = 0;
for (int i = 0; i < intArray.Length; i++)
{
if (intArray[i] == intArray[intArray[i] - 1])
{
return intArray[i];
}
else if( intArray[i]-1 !=i)
{
temp = intArray[intArray[i] - 1];
intArray[intArray[i] - 1] = intArray[i];
bool b = true;
do
{
if (temp - 1 == i)
{
intArray[i] = temp;
b = false;
}
else
{
if (temp == intArray[temp - 1])
{
return temp;
}
intArray[i] = intArray[temp - 1];
intArray[temp - 1] = temp;
temp = intArray[i];
}
} while (b);
}
}
throw new Exception("No duplicate found!");
}
n(n+1)/2-(sum of numbers)
ReplyDeletelets say n=10
ReplyDeleteint getMissingNumber(int[] s)
int[] num = new int[10];
int tmp=0, i=0, n=10, dup=0;
while (i<n){
tmp=s[i++];
if((num[tmp]+tmp)/2 == tmp) dup=tmp;
num[tmp]=tmp;
sum+=tmp;
}
return((n*(n+1)/2) - (sum-tmp))
}
i dnt know
ReplyDeletepublic class MissingNumber {
ReplyDeletepublic static void main(String[] args) {
int n;
int result;
int[] anArray;
anArray = new int[6];
anArray[0] = 1;
anArray[1] = 2;
anArray[2] = 4;
anArray[3] = 5;
anArray[4] = 3;
anArray[5] = 6;
n = 6;
result = MissingNumber(1,n,anArray);
System.out.println(result);
}
public static int MissingNumber(int p, int q, int[] a){
if (a[p-1]!=p)
{
return p;
}
else if(a[q-1]!=q)
{
return q;
}
else
{
return MissingNumber(p+1,q-1,a);
}
}
}