Solve it!!! Intresting One!!!

asadullah.ansari's Avatar, Join Date: Jan 2008
TechCake
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.

Last edited by asadullah.ansari; 30Apr2008 at 19:50..
blabla2028's Avatar
Light Poster
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's Avatar
Light Poster
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's Avatar
Light Poster
the result int avariable must be set to 1 since the beginning
blabla2028's Avatar
Light Poster
also supposing the two array sizes are equal. n=n2
asadullah.ansari's Avatar, Join Date: Jan 2008
TechCake
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<n2; counter1++)
{
for(counter2=0; counter2<n; counter2++)
{
if counter2=counter1 continue;
result=result*arr[counter2];
}
OutVar[counter1]=result;
result=1;
}

}
[/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's Avatar, Join Date: Apr 2008
Newbie Member
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's Avatar, Join Date: Apr 2008
Newbie Member
Soorry, 'i' is wrong it will be 'cnt' everywhere in the previous one.
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
When using code block try indenting your code so that its easy to read for others.
asadullah.ansari's Avatar, Join Date: Jan 2008
TechCake
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.