Arrays

[icontspelll]

multiply all elements in an array by every but the corresponding element in another array. Without division and without using n^2 calculations (no nested loops or similar).

[vlad from moscow]

I have not understood the assignment but I think that a recursion will help.:)

void product( int a[], const int b[], int n )
{
   if ( n-- )
   {
      a[n] *= b[n];
      product( a, b, n );
   }
}

[icontspelll]

Example solution

a[n] and b[n] where n=4 the numbers in the array a [1,2,3,4]
when n=1 b[n] of I would equal 2×3×4=24
when n=2 b[n] of I would equal 1×3×4= 12
when n=3 b[n] of I would equal 1x2×4=8
when n=4 b[n] of I would equal 1x2×3=6

final answer:
all, 2,3, 4] and b[24,12,8,6]

This must work for all n.

[vlad from moscow]

Well, when I can suggest the following function

void compute( const int a[], int b[], unsigned n, unsigned k )
{
	if ( k == 0 ) return;

	if ( k == 1 )
	{
		for ( unsigned i = 0; i < n; i++ ) b[i] = 1;
		return;
	}

	compute( a, b, n, --k );

	for ( unsigned i = 0, j = k; i < n; i++ )
	{
		b[i] *= a[j];
		if ( ++j == n ) j = 0;
	}
}

For example

int a[4] = { 1, 2, 3, 4 };
int b[4];

compute( a, b, 4, 4 );

[Gaminic]

Shortened logic:

b[i] = product(j = 0->n)[a[j]]/a[i] (2n calculations, but using division)

Alternative logic:

For any value 'i', the array 'a' is split into two partitions: [0,i[ and ]i, n]. Using a temporary array ('c'), you can calculate the "partitions" value for all values of 'i' in 2*(n-1) calculations (n-1 forward, n-1 backward). Then, for any 'i', the final value b[i] = c[i-1]*c[i+1].
(In words: the value of b[i] is the product of the forward partition up to i-1 multiplied by the product of the backward partition down to i+1. By definition, this is the product of all numbers excluding the i'th.)

[edit]

Roughly 2(n-1)+n calculations.

[vlad from moscow]

Here is the complete test program written in MS VC++ 2010

#include "stdafx.h"
#include	<iostream>
#include	<numeric>
#include	<vector>

void compute( const int a[], int b[], unsigned n, unsigned k )
{
	if ( k == 0 ) return;

	if ( k == 1 )
	{
		for ( unsigned i = 0; i < n; i++ ) b[i] = 1;
		return;
	}

	compute( a, b, n, --k );

	for ( unsigned i = 0, j = k; i < n; i++ )
	{
		b[i] *= a[j];
		if ( ++j == n ) j = 0;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int n;

	while ( std::cout << "\nEnter array size: ", std::cin >> n && n != 0 )
	{
		std::vector<int> a( n );
		std::vector<int> b( n );

		std::iota( a.begin(), a.end(), 1 );
		compute( a.data(), b.data(), n, n );

		for ( int i = 0; i < n; i++ )
		{
			std::cout << b[i] << ' ';
		}
		std::cout << std::endl;
	}

	return ( 0 );
}