CareerCup

+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.

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

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;
}

Could you please provide java or c code implement this?

100! is so big that no type can hold it

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

@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.

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.

@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).

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.

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

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

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 ????

}