Each element of an integer array is replaced by the product of all the other elements in the array

Question

0.00/5 (No votes)

See more:

>Function has two arguments - (i) array (ii) its size (n)
>Each element of the array will be replaced by the product of the other elements .
>For example if the following is the array -{3, 2, 1}
the function would return the following output - {2,3,6}.
>This is not a homework problem . I don't want you to do it . I just want to optimize my program .
>Thank you.

What I have tried:

I have attached the code of my function.
As you can see , I have used an array [temp] to store the product of the elements but I have to initialize every element as 1 manually .
>Is there any better way to do it ?
>Could you give any hints as to how I can improve the time complexity of the code?

void multiply_input(int str[],int n)
    {
        int temp[25]={1,1,1,1,1,1,1,1,1,1,1,1,1};
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i!=j)
                    temp[i]=temp[i]*str[j];


            }

        }
        for(int k=0;k<n;k++)
            cout<<" "<<temp[k];

Posted 30-May-18 6:19am

Regista6

Updated 30-May-18 17:42pm

v2

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2018-05-30T06:33:00

For the initialization, try:
Try:

C++

int temp[25];
for (int i = 0; i < 24; i++)
   {
   temp[i] = 1;
   }

Or read the values from a file, or the user.

As for the time complexity, this is homework (whether you like it or not) so I'll give you no code.

But ... think about it.
Do one pass through the whole array, to work out the product of all values.
Do a second pass through the whole array, to replace each element with that total divided by the original value of the cell.

Patrice T · Accepted Answer · 2018-05-30T08:21:00

Quote:
Could you give any hints as to how I can improve the time complexity of the code?

Your code runtime complexity is O(n²) and memory complexity is O(2n) because of temp array.

With the method of OG (with division), the runtime complexity is O(n) and memory complexity is O(n).

Since the only thing you do with temp array is printing the value, you don't need the array, once you got the product, print it.
Your code runtime complexity will be O(n²) and memory complexity will be O(n).
If you really need to replace the values of str, it is a little more complicated, but a variable with partial product is enough to do it.

Rick York · Accepted Answer · 2018-05-30T17:44:00

There is one way to make it not be O(n squared) and instead be O(2n) and a temporary array is not required. To do this, first calculate the product of all values in the array. That is pass one. Then step through the array again and each element will be the product divided by the element already in the array. The reason this works is, let's say we have a three element array. Item 1 is the product of items 0 and 2. To give them letters, b = a * c. To use this algorithm, the product is p = a * b * c and the new b is = p / bOld which is ( a * b * c ) / b and that reduces to b = a * c. This second pass makes it O(2n) and the only value stored is the initial product of the array.

The risk to this approach is the possibility the product will overflow. If the values are constrained and a sixty-four bit product is used that will reduce the risk. Of course, that is also a risk with the O(n squared) approach but it has one less factor in each product. One flaw it has is the result goes out the window if one or more values are zero. This can be one of the constraints given to the values though ie., values must range from 1 to 32K or something like that. It just happens that 32K is RAND_MAX, the largest value returned by rand(), so it is a convenient value to use.

Each element of an integer array is replaced by the product of all the other elements in the array

3 solutions

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0