in this Problem if the array is
A[n] = {a0,a1,....a(n-1),a(n)}
after the second iteration,
the value will be
{a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,........, a(n-2)-2a(n-1)+a(n)}
if we add all these terms then
all the middle elements will be canceled out so the remaining will be.
{a0-a2 - a(n-1)+a(n)}
which can be written as a general form
solution: - {a(n)-a(n-1)} - {a2-a0}
this will solve the problem in time complexity in O(1).
example: A = {5, 3, 8, 9, 16}
solution : - {16-9}-{3-5}
{7} - {-2}
9
On Wed, Apr 10, 2013 at 7:03 AM, Shashwat Anand <[email protected]
<mailto:[email protected]>> wrote:
On 4/10/13 12:13 AM, rahul sharma wrote:
If you have any other solution ..please post that...i thnik
recursion is ok with base case...we need to scan again after
first iteration...??
First of all, the array size and number of iteration both won't be
N or else the answer will always be 0.
I take the following assumption, array have K elements and number
of iteration is N.
Now, if N >= K, the return value will always be 0.
For rest, we can decompose the array following the rule of
adjacent element difference.
Solution with O(NK) time complexity follows:
int
doit (vector <int> v, int N) {
int k = (int) v.size () - 1;
if (N > k) return 0;
int c = 1;
while (N--) {
for (int i = k; i >= c; i--)
v [i] -= v [i - 1];
for (int i = 0; i < c; i++)
v [i] = 0;
c++;
}
return accumulate (v.begin (), v.end (), 0);
}
int
main ()
int a [] = { 5, 3, 8, 9, 16 };
vector <int> v (a, a + sizeof (a) / sizeof (a [0]));
assert (doit (v, 0) == 41);
assert (doit (v, 1) == 11);
assert (doit (v, 2) == 9);
assert (doit (v, 3) == -1);
assert (doit (v, 4) == 21);
assert (doit (v, 5) == 0);
return 0;
}
However, I /strongly believe/ the solution can be done in *linear
time*. To code this with quadratic time complexity is a no-brainer.
So, I took the array with K = 6 elements and decomposed.
N = 0: [a1, a2, a3, a4, a5, a6] => a1 + a2 + a3 + a4 + a4 + a6
N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] => a6 - a1
N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 -
2a5 + a4] => a6 - a5 - a2 + a1 => (a6 - a5) - (a2 - a1)
N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5
+ 3a4 - a3] => a6 - 2a5 +a4 - a3 + 2a2 - a1
N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 -
4a3 + a2] => a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1
N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] => a6 -
5a5 + 10a4 - 10a3 + 5a2 - a1
N >= 6: [0, 0, 0, 0, 0, 0] => 0
The resulting solution does show some property of Binomial
coefficient as pointed out by @Don in his hint (Pascal triangle).
I suppose this shall be the way to attack this problem.
On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma
<[email protected] <mailto:[email protected]>> wrote:
i forgot to add base case..can add wen 2 elemnts are there
then there sum is stored and we reurn from there...i m in
hurry,,,sry for that,,
On Wed, Apr 10, 2013 at 12:11 AM, Don <[email protected]
<mailto:[email protected]>> wrote:
It is O(N^2) because the inner loop takes N steps to
execute and that
loop will be executed N times.
However, I would suggest not using recursion. There is no
reason to
not do it iteratively. Your recursive solution has no
base case so it
will recurse until your computer runs out of stack space,
at which
point it will crash.
Don
On Apr 9, 2:29 pm, rahul sharma <[email protected]
<mailto:[email protected]>> wrote:
> A = {5, 3, 8, 9, 16}
> After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
> After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
> Given an array, return sum after n iterations
>
> my sol/
> void abc(int arr[],n)
> {
> for(i=0;i<n;i++)
> arr[i]=arr[i+1]-arr[i];
> abc(arr,n-1);
>
> }
>
> I wana ask that the complexity is o(n) or o(n)2......as
loop is executed n
> times..say n is 10...so fxn is called 10 times....i.e
10 n..and ignoring n
> it comes out to be...n......but if we implemeted with 2
loops then
> complexity is n2 ...and both sol are taking same no of
iterations...please
> tell whether complexity is n or n2 for above code....if
it is n2 then how???
--
You received this message because you are subscribed to
the Google Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails
from it, send an email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit
https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the
Google Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to [email protected]
<mailto:[email protected]>.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to [email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit https://groups.google.com/groups/opt_out.
--
Regards,
Pankaj Kumar Joshi
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
