## Siemens Interview Question for Java Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

stackoverflow.com/questions/10218791/find-two-missing-numbers

Comment hidden because of low score. Click to expand.
0

+1 I think the answer at stackoverflow is the closest answer. However, it's still not O(1) as claimed, because you need to iterate the array to calculate the actual sum and the squared sum of the array.

If the sum of all numbers and the sum of squares of all numbers of the array are not given, this question cannot be solved in less than linear time.

Comment hidden because of low score. Click to expand.
0

It claims to use O(1) memory, not O(1) time. It takes ~2n time (O(n))

Comment hidden because of low score. Click to expand.
0

The code for the stackoverflow link:

``````#include <bits/stdc++.h>

using namespace std;

int main () {
int n;
scanf("%d",&n);

int Nsum = 0;
int NSsum = 0;

Nsum = (n*(n+1))/2;
NSsum = n*(n+1)*(2*n+1)/6;

vector < int > v (n+1, 0);

int sum = 0;
int Ssum = 0;

for (int i=0; i<n-2; i++) {
scanf("%d",&v[i]);
sum = sum + v[i];
Ssum = Ssum + v[i]*v[i];
}

int aplusb = Nsum - sum;
int asqplusbsq = NSsum - Ssum;

int twoab = aplusb * aplusb - asqplusbsq;
int aminusb = int(sqrt(asqplusbsq - twoab));

int x = (aplusb + aminusb)/2;
int y = (aplusb - aminusb)/2;

cout << x << "x " << y << "y " << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I doubts if this can be solved in less than time O(N)

Comment hidden because of low score. Click to expand.
0
of 2 vote

Sum of the missing numbers = (100*101)/2 - Add all numbers
Product of the missing numbers = product of 100 numbers/ product of actual numbers
Use above both to find out missing numbers

Comment hidden because of low score. Click to expand.
0

Could you please provide java or c code implement this?

Comment hidden because of low score. Click to expand.
1

100! is so big that no type can hold it

Comment hidden because of low score. Click to expand.
1
of 1 vote

He already mentioned, that we should not traverse the complete Array. Then how can you find the sum of complete Array

Comment hidden because of low score. Click to expand.
1
of 1 vote

@prashantreddy: Isn't it obvious you have to look at at least Omega(n) numbers? i.e. the restriction is bogus, and made up by the person asking the question.

Comment hidden because of low score. Click to expand.
0

As @Sylla pointed out 100! is a very large number and won't fit in any basic primitive data type. You can argue that you can use a language that supports big numbers like Python or Java, but then I don't think that's the intention. @dn suggested the link at stackoverlow and that solution seems more reasonable. Using sum of numbers and sum of square of numbers, which both can be calculated with Gaussian formulas.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@oOZz: Even if you use Python or something like BigInteger in Java, you have to consider how those operations are implemented behind the covers. They are not O(1). Behind the covers, a single oversized integer has to be stored as a (possibly large) array of ints, longs, bytes, or other primitives (implementation-dependent). To compute a sum or product, the array representing the number has to be iterated over. There's no wand that a computer can waive to magically take huge numbers and multiply them together in one step. The language / library has to apply an algorithm that iterates over and operates on the underlying array of primitive types.

The cost of addition can be expected to be O(k) to add two k-digit numbers. Multiplication is at least O(k log k), but can be more depending on the implementation (is O(k^2) in the naive implementation).

Comment hidden because of low score. Click to expand.
0

It will not work in practice - 100! = 9.3326215443944152681699238856267e+157. Compared with Sum(1,100) = 5050 the difference is too big to solve the equation with acceptable precision.

Comment hidden because of low score. Click to expand.
0

you reallly dont need to calculate 100! factorial . 100! / product of given numbers. .you need to use multiplication and division to keep the calculation under overflow. and there is no way you could solve this problem without traversing the entire numbers

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nice Thanks Siva :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Prashant: Code is pretty simple. Let's do sum mathematics first...
Let a and b are the missing numbers.

{
Sum of 100 num = Sum of 98 num + a +b
=> a + b = (Sum of 100 num ) - (Sum of 98 num ) = x suppose

Product of 100 num = Product of 98 num * a *b
=> a*b = Product of 100 num /Product of 98 num = y suppose

x and y are known. We need to find a and b

a+b = x -----1
a*b = y .......2

(a-b)^2 = (a+b)^2 - 4ab
From 1 and 2
=> a-b = sqrt(x^2 - 4y) = z suppose
a + b = x

=> a = (x+z)/2
b = x - b
}

I dont think any special coding skills neede to write a program for this. :)

Comment hidden because of low score. Click to expand.
1
of 1 vote

Finding Sum and product of given numbers takes O(n) time complexity and yes I dont think it is possible with lesser time complexity

Comment hidden because of low score. Click to expand.
0

I agree ..it looks pretty simple but i am not able to implement this in java.. I am not sure how to find out a and b after computing sum and product of missing number

``````public static void main(String[] args) {

int arr[]={2,1,4,6,5,8,9,10};

int finalSum = 10*(10+1)/2 ;
int finalProduct = 1*2*3*4*5*6*7*8*9*10;

// a and b are missing number
int a = 0,b = 0;

// product if missing number
int t1 = finalProduct/(1*2*4*5*6*8*9*10);

// sum of missing number
int t2 = finalSum - (1+2+4+5+6+8+9+10);

// Find out a and b ????``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you generalize this, find missing n numbers.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is nearly impossible to solve in less than O(n)..

-Solving n! and etc. etc. is really hectic task.
-Still we can generalize questions like this with "k" missing numbers by using an extra arrays.
-Using one extra Arrays you would take O(n) time to find all the missing "K" numbers.
LOGIC:
1.)Initialize all the elements of extra array to zero.
2.)Traverse the given array form the beginning.
3.)Replace zero with one in the extra array at the index of the element found.
eg: if 57 is found in the given array then replace - extra[57] with 1.
4.)At the end traverse the extra array and note down the index values of the places having 0.

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{"You can find out the missing number in array by following algorithm: /* getMissingNumber takes array and size of array as arguments*/ int getMissingNumber (int arr[], int num) { int i; /* For xor of all the elemets in arary */ int x1 = a[0]; /* For xor of all the elemets from 1 to n+1 */ int x2 = 1; for (i = 1; i< n; i++) x1 = x1^a[i]; for ( i = 2; i <= n+1; i++) x2 = x2^i; return (x1^x2); } I also found some more possible solutions. you can check out below link for more solutions: <br/><br/> newtechnobuzzz.blogspot.in/2014/07/find-out-missing-number-in-array-in-java.html
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ You can find out the missing number in array by following algorithm: /* getMissingNumber takes array and size of array as arguments*/ int getMissingNumber (int arr[], int num) { int i; /* For xor of all the elemets in arary */ int x1 = a[0]; /* For xor of all the elemets from 1 to n+1 */ int x2 = 1; for (i = 1; i< n; i++) x1 = x1^a[i]; for ( i = 2; i <= n+1; i++) x2 = x2^i; return (x1^x2); } I also found some more possible solutions. you can check out below link for more solutions: newtechnobuzzz.blogspot.in/2014/07/find-out-missing-number-in-array-in-java.html
Comment hidden because of low score. Click to expand.
0
of 0 vote

newtechnobuzzz.blogspot.in/2014/07/find-out-missing-number-in-array-in-java.html

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.