Arrays and Bitwise - Page 2

[invisal]

Considering the first problem, You guys have come up with brilliant answers which is taking me more than 20 minutes to understand. Did not someone gave a link to an easier answer so that a novice like me could understand.

Add all the element in the array subtract 1000 * 1001 / 2. The answer is the duplicate. Hope I am right

That is wrong.

• Let say X represent the duplicate number.
• And Y represent the missing number.
• 1 + 2 + + .... + 1000 + X - Y = Z
• Z represent the sum of array.
• So X - Y = Z - (1000*1001/2)
• Then, the result of your answer is the difference between the missing number and duplicate number.

[Prabakar]

I have no other choice but to accept what you say!

[invisal]

The first problem has been bothered me alot while I was doing my school-assignment so now I got a chance to solve it now. I think this problem can be solve by using mathematic.

• Let say A is the sum of the array.
• and X is a duplicate number and Y is a missing number.
• so A = 1 + 2 + .... + 1000 + X - Y
• Then, A = (1000 * 1001 / 2) + X - Y
• X - Y = A - (1000 * 1001 / 2)
• Let say B is the result of multiply of all the array element.
• The result of the B is probally the result of multiply of all non-duplicate number and the double of duplicate number.
• Then C = B / 1000! = X / Y
• Now we got: C = X / Y and X - Y = A - (1000 * 1001 / 2)
• X = Y * C
• Y * C - Y = A - (1000 * 1001/2)
• Y * (C - 1) = A - (1000 * 1001/2)
• Y = [A - (1000 * 1001/2)] / (C - 1)
• Now we know the missing number (Y) it is easy to find the duplicate number
• X = Y + [A - (1000 * 1001/2)]

[vijayan121]

this makes only one pass through the array (breaking when the duplicate is found).
however, the requirement 'You can access each array member only once' is violated.
also, it modifies the array as it goes along; perhaps even this is not allowed.

int duplicate_number( int* array, std::size_t N )
{
  for ( std::size_t i = 0 ; i<N ; ++i )
  {
    int number = array[i] > 0 ? array[i] : -array[i] ;
    number = number -1 ; // [1,N] => [0,N-1] 
    
    // use negative value to mark the number 
    if( array[number] > 0 ) array[number] = -array[number] ;
    else return number+1 ; // already marked earlier; duplicate
  }
}

[invisal]

I think in my method, I only need to access the array once.

int sum = 0, lsum = 0;
float c = 1;

for(int i = 0; i < 1000; i++) {
   c *= ((sum += array[i]) - lsum) / (i + 1);
   lsum = sum;
}
// in the end we got   c = x/y
// and sum = (1000 * 1001/2) + x - y

[vijayan121]

yes, you can compute the sum and product in one go.
however, floating point arithmetic would not give correct results.
you would need to use a big integer type.

[invisal]

I have to agree that the float type is not very accurate. I was wondering whether it is accurate enough to produce a correct answer :(

[Alex Edwards]

int x = 21;
	x = (x << 2) + (x << 1) + x; //multiply number by 7
	cout << x;

Can you not shift 0, or did you feel it was redundant?