CareerCup

If I recall correctly, in this problem, division was not allowed.

I would like to know if I have understood the question correctly.

Input and Index are two integer arrays each of size n.For example if n=5 the size of each array is 5.

Let us say the input array contans following elements 3,5,6,7,8 that is input[0]=3 input[1]=5 input[2]=6 input[3]=7 input[4]=8

similarly index array is also populated.
index[0]=18 index[1]=4 index[2]=30 index[3]=5 index[4]=10

considering that result[i] is product of all elements in input except the element at input[index[i]].Now when i=0 i have index[0]=18 i dont have an element at input[18] as the size is 5,so will the product be all elements from input[0] till input[4] =5040.

and when i=1 index[1]=4 hence input[4] is excluded and the product of the rest is caculated ie 3*5*6*7=630

Does it makes sure that input array does not go out of limit(i cant use index word here:D) so question should provide that index array should contain numbers between 0 and n-1.

for (int i = 0; i != n; ++i) {
    result[i] = 1;
}

for (int i = 0; i != n; ++i) {
    if (index[i] != i) {
        result[i] *= input[i];
    }
}

Would this work?

Just another way of doing this. Create an array v2 whose elements are the product of all elements of v1 except the element at that index. Then re-arrange as required by the index array. Takes 3 parses of O(n).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void transform (int* v1, int* index, int* v2, const int& size) {
int p = 1;

for (int i = 0; i < size - 1; ++i) {
p *= v1[i];
v2[i+1] = p;
}

p = 1;
for (int i = size - 1; i > 0; --i) {
p *= v1[i];
v2[i-1] *= p;
}

for (int i = 0; i < size; ++i) {
swap(v2[index[i]], v2[i]);
swap(index[index[i]], index[i]);
}
}

int main() {
int v1[] = {1,2,3,4,5};
int v2[] = {1,1,1,1,1};
int index[] = {4,2,1,3,0};

transform(v1, index, v2, 5);

copy(v2, v2 + 5, ostream_iterator<int>(cout, " "));
cout << endl;

return 0;
}

O(n) algorithm with O(1) memory. This algorithm traverses both the arrays twice, once calculation product of numbers on the left and then calculating products on the right side. The result of this traversals is written in the results array.

int[] arr1 = { 1, 2, 3 };
                int[] arr2 = { 10, 20, 30 };
                int[] output = new int[arr1.Length];

                int leftProd = 1;
                for (int i = 0; i < arr1.Length; i++)
                {
                    output[i] *= leftProd;
                    leftProd *= arr1[i];
                }

                int rightProd = 1;
                for (int i = arr1.Length - 1; i >= 0; i--)
                {
                    output[i] *= rightProd;
                    rightProd *= arr1[i];
                }

                leftProd = 1;
                for (int i = 0; i < arr2.Length; i++)
                {
                    output[i] *= leftProd;
                    leftProd *= arr2[i];
                }

                rightProd = 1;
                for (int i = arr2.Length - 1; i >= 0; i--)
                {
                    output[i] *= rightProd;
                    rightProd *= arr2[i];
                }

                
                output.ToList().ForEach(Console.WriteLine);

Another shot at the problem.

public void ProductOfArrayElements()
{
    int[] inputArr = { 1, 2, 3 };
    int[] indexArr = { 2, 0, 1 };
    int[] output = new int[inputArr.Length];


    int leftProd = 1;
    for (int i = 0; i < inputArr.Length; i++)
    {
        output[ i ] = leftProd;
        leftProd *= inputArr[indexArr[i]];
    }

    int rightProd = 1;
    for (int i = inputArr.Length - 1; i >= 0; i--)
    {
        output[i] *= rightProd;
        rightProd *= inputArr[indexArr[i]];
    }

    output.ToList().ForEach(Console.WriteLine);

    // Output is [2, 6, 3 ]
    // 2 = 1 * 2  ( skipping inputArr[2])
    // 6 = 2 * 3  ( skipping inputArr[0])
    // 3 = 1 * 3  ( skipping inputArr[1])
}

<pre lang="" line="1" title="CodeMonkey78619" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
getpro(int arr[],int n,int out[])
{
int prod=1,x=1;
for(int i=0;i<n;i++)
prod=prod*arr[i];

for(i=0;i<n;i++)
{
x=1;
while(x*arr[i]!=prod)
x++;
out[i]=x;
}
}

</pre><pre title="CodeMonkey78619" input="yes">what is the time complexity for dis code??? somebody help</pre>

If I understand it correctly, then the function should find product of the entire array elements of input except the element at particular index in the index array:

long mul = 1;
for (i=0 to n)
mul*= input[i];

for(i=0 to n){
result[i] = mul / input[index[i]];
}