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]> 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]>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]> 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]> 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].
>>> 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].
> 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].
> 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.
