Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Solve it!!! Intresting One!!! (http://www.go4expert.com/forums/solve-intresting-t10292/)

Solve it!!! Intresting One!!!

Can you Anyone solve this problem...

There is given one array lets say Arr[n]( n is the size of array). You have to store multiplication of all elements of Arr[n] except element Arr[i] into a array OutVar[i]. Example:
Code:

```    Suppose given am array as     Arr[5]={1,2,3,4,5}     Then     OutVar[0]=Arr[1]*Arr[2]*Arr[3]*Arr[4]     OutVar[1]=Arr[0]*Arr[2]*Arr[3]*Arr[4]     OutVar[2]=Arr[0]*Arr[1]*Arr[3]*Arr[4]     OutVar[3]=Arr[0]*Arr[1]*Arr[2]*Arr[4]     OutVar[4]=Arr[0]*Arr[1]*Arr[2]*Arr[3]*```
Condition Apply: 1. Time Complexity should be O(n) (No matter for space better If you
minimize space also)
2. Division(/) or Modular division(%) are not allowed.

 blabla2028 30Apr2008 04:14

Re: Solve it!!! Intresting One!!!

The code would be something like this I suppose:

Code:

```int main() { int arr[n],OutVar[n2]; int counter1,counter2,result; result=0; for(counter1=0; counter1<n2; counter1++) { for(counter2=0; counter2<n; counter2++) { if counter2=counter1 continue; result=result*arr[counter2]; } OutVar[counter1]=result; result=1; } }```

 blabla2028 30Apr2008 04:17

Re: Solve it!!! Intresting One!!!

The code would be something like this I suppose:

Code:

```int main() { int arr[n],OutVar[n2]; int counter1,counter2,result; result=1; for(counter1=0; counter1<n2; counter1++) { for(counter2=0; counter2<n; counter2++) { if counter2=counter1 continue; result=result*arr[counter2]; } OutVar[counter1]=result; result=1; } }```

 blabla2028 30Apr2008 04:18

Re: Solve it!!! Intresting One!!!

the result int avariable must be set to 1 since the beginning

 blabla2028 30Apr2008 04:22

Re: Solve it!!! Intresting One!!!

also supposing the two array sizes are equal. n=n2

Re: Solve it!!! Intresting One!!!

Quote:
 Originally Posted by blabla2028 The code would be something like this I suppose: [CODE] int main() { int arr[n],OutVar[n2]; int counter1,counter2,result; result=1; for(counter1=0; counter1
[/QUOTE]

Nice Appreciated!!! But dear One thing Time complexity of your program is O(n2 *n) ~=O(sqr(n))
But you have to solve it in time O(n) i.e. Linear.

 subha040680 30Apr2008 11:02

Re: Solve it!!! Intresting One!!!

Can this be the solution?

Code:

```void main() {   for(int cnt = 0; cnt < 5; ++cnt)   {     OutVar[cnt] = Arr[(i+1)%5] *Arr[(i+2)%5]*Arr[(i+3)%5]*Arr[(i+4)%5];   } }```

 subha040680 30Apr2008 11:04

Re: Solve it!!! Intresting One!!!

Soorry, 'i' is wrong it will be 'cnt' everywhere in the previous one.

 shabbir 30Apr2008 11:47

Re: Solve it!!! Intresting One!!!

When using code block try indenting your code so that its easy to read for others.

Re: Solve it!!! Intresting One!!!

Quote:
 Originally Posted by subha040680 Can this be the solution? Code: ```void main() {   for(int cnt = 0; cnt < 5; ++cnt)   {     OutVar[cnt] = Arr[(i+1)%5] *Arr[(i+2)%5]*Arr[(i+3)%5]*Arr[(i+4)%5];   } }```
Nice approch!!! But sorry dear i forgot to mention you cant use division or modular division operator.

 All times are GMT +5.5. The time now is 21:56.