Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forumdisplay.php?f=20)
-   -   Solve it!!! Intresting One!!! (http://www.go4expert.com/showthread.php?t=10292)

asadullah.ansari 29Apr2008 18:42
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

asadullah.ansari 30Apr2008 10:02
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<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 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.

asadullah.ansari 30Apr2008 19:49
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 07:43.