## Re:"Odd" TP question

In article <364AEE61.749AE...@rug.ac.be>, Ike.Castel...@rug.ac.be says...

##### Quote

>You can use the odd-command in pascal.

>var

> cointer, sum, number : integer;

>begin

> sum := 0;

> read (number);

> for cointer := 1 to number do

> begin

> if odd(cointer) do

> sum := sum + cointer;

> end;

>write (sum);

>end;

You are absolutely correct.

But there is an alternative solution which is much faster when N is large.

Suppose there is a second problem which ask the sum of 1 to 100.

Instead of using a loop to sum that one by one, we can simply use

symmetry

1 2 3 ........ 98 99 100

There are 50 pairs of {[100 + 1], [99 + 2], [98 + 3], ...}.

So the answer will be 101*50=5050.

Return back to the original problem (i.e. sum odd from 1 to N).

Here is an alternative solution using similar symmetry trick, as below.

Function sum_odd_by_symmetry ( N : integer) : integer;

var

tmp, M, sum : integer;

begin

if odd(N) then

begin

tmp := (N + 1) div 2; { N + 1 equals sum of such a pair}

{ Divide it by 2 to count only half of odd & even}

sum := tmp * tmp; { tmp also equal the number of such pairs}

end

else

begin

M := N - 1; {if N is even, count it down by 1 to get the odd}

tmp := N div 2; { N equals sum of such a pair}

{ Divide it by 2 to count only half of odd & even}

sum := tmp * tmp; { tmp also equal the number of such pairs}

end;

sum_odd_by_symmetry := sum;

end;

Check with both approaches, they both return the same answer :)

You can even do it by hand without a computer if you understand the trick.