How Many Ways to Solve this Problem? Add the Sequential Numbers x Through y

13 07 2011

July 13, 2011

I am not entirely sure why, however a couple of days ago the following search keywords were used to access one or more articles on this blog:

the sum of 1+2+3+4...+98+99+100

The above request I found to be a bit interesting, and there is a 50/50 chance that the person found the right answer to the sum of the numbers between 1 and 100. 

If you had to solve this problem with the help of Oracle Database, how would you accomplish the task?  If it helps, I think that I recall that the mathematical notation representing the problem posed by the searcher is as follows:

Would your answer be any different if the person needed to know the sum of the numbers between 6 and 105:

What about generalizing the problem even further:

Think about the problem before scrolling down.  How many unique solutions are able to produce the answer?

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

————————————

If you think about the problem, in its simplist form it is really just a matter of repeatedly adding the set of the highest and lowest unmatched numbers (all of those results should be the same, otherwise your calculator needs new batteries) and then multiplying by the number of pairs (1/2 as many numbers are in the sequence to be summed):

01 + 100 = 101
02 + 99 = 101
03 + 98 = 101
04 + 97 = 101
05 + 96 = 101
...
50 + 51 = 101

So, the general formula is:

(max - min + 1) / 2 * (min + max)

And the SQL statements to produce the results:

SELECT   (100 - 1 + 1) /2 * (1 + 100) FROM   DUAL;  
SELECT   (105 - 6 + 1) /2 * (6 + 105) FROM   DUAL;

————————————

–

–

–

–

–

–

–

–

–

–

–

–

For now, ignore the above section.  How many ways can this particular problem be solved with the help of Oracle Database?  Are there any built-in functions that will help?

« »


Actions

Information

  • Date : July 13, 2011
  • Categories : SQL

25 responses

13 07 2011
Enrique Aviles (07:23:51) :

select sum(x)
from (select rownum x from dual connect by level <= y)
where r between x and y

Reply
13 07 2011
Enrique Aviles (07:46:09) :

Correction:

Declare x and y as number variables.

select sum(r)
from (select rownum r from dual connect by level <= y)
where r between x and y;
Reply
13 07 2011
Charles Hooper (14:49:12) :

Enrique,

The first solution that I thought about is similar to what you posted, and then I started wondering… what if the lower number is not 1, but instead some other number. I abandoned my solution that was similar to your solution before sliding the CONNECT BY portion of the query into an inline view as you did:

VARIABLE X NUMBER
VARIABLE Y NUMBER
EXEC :X := 6
EXEC :Y := 105
 
select sum(r)
from (select rownum r from dual connect by level <= :y)
where r between :X and :y;
 
    SUM(R)
----------
      5550

EXEC :Y := 104
 
select sum(r)
from (select rownum r from dual connect by level <= :y)
where r between :X and :y;
 
    SUM(R)
----------
      5445

Those are the expected values.

Reply
13 07 2011
Raj (07:31:04) :

One way of solving it mathematically is applying this formula => (n * (n + 1)) / 2

So in this case it will be ((y – x + 1) * (y – x + 2)) / 2

Reply
13 07 2011
Raj (07:42:07) :

Above formula is incorrect. Instead it should be something like this.

  1  declare
  2     l_start number;
  3     l_end number;
  4     l_Tot number;
  5  begin
  6      l_Start := 1;
  7      l_end   := 100;
  8      l_tot := l_end * (l_end + 1) / 2;
  9      dbms_output.put_line(l_tot);
 10      l_tot := l_tot - ((l_start - 1) * (l_Start) / 2);
 11      dbms_output.put_line(l_tot);
 12* end;

Thanks

Reply
13 07 2011
Charles Hooper (14:13:48) :

Raj,

This is the output that I receive:

SET SERVEROUTPUT ON
 
declare
l_start number;
l_end number;
l_Tot number;
begin
l_Start := 1;
l_end := 100;
l_tot := l_end * (l_end + 1) / 2;
dbms_output.put_line(l_tot);
l_tot := l_tot – ((l_start – 1) * (l_Start) / 2);
dbms_output.put_line(l_tot);
end;
/
 
5050
5050

PL/SQL procedure successfully completed.

SET SERVEROUTPUT ON
 
declare
l_start number;
l_end number;
l_Tot number;
begin
l_Start := 6;
l_end := 105;
l_tot := l_end * (l_end + 1) / 2;
dbms_output.put_line(l_tot);
l_tot := l_tot – ((l_start – 1) * (l_Start) / 2);
dbms_output.put_line(l_tot);
end;
/
 
5565
5550

PL/SQL procedure successfully completed.

SET SERVEROUTPUT ON
 
declare
l_start number;
l_end number;
l_Tot number;
begin
l_Start := 6;
l_end := 104;
l_tot := l_end * (l_end + 1) / 2;
dbms_output.put_line(l_tot);
l_tot := l_tot – ((l_start – 1) * (l_Start) / 2);
dbms_output.put_line(l_tot);
end;
/
 
5460
5445

PL/SQL procedure successfully completed.

It appears that your PL/SQL block is producing the expected value (I assume that the first DBMS_OUTPUT is showing the value before correction).

Reply
14 07 2011
Raj (03:11:54) :

That’s correct. It was included just for my testing purpose.

Thanks

Reply
13 07 2011
Mr Py (07:50:34) : 
select sum(level) from dual where level>6 connect by level<=105;
Reply
13 07 2011
Charles Hooper (14:03:10) :

Mr Py,

Before testing, I thought that your example would fail for the same reason that a SQL statement would fail if the ROWNUM pseudo column is used in the WHERE clause – as testing shows, that was not the case. Unfortunately, it appears that the = sign just after the number 6 was lost during formatting of your comment:

SQL> select sum(level) from dual where level>6 connect by level<=105;
 
SUM(LEVEL)
----------
      5544

SQL> select sum(level) from dual where level>=6 connect by level<=105;
 
SUM(LEVEL)
----------
      5550
Reply
13 07 2011
Dom Brooks (08:34:14) :

How long is a piece of string?
The number of variations on a theme would mean that there are soooo many “different” ways.
Two basic strategies though:
– one is to generate the formula as a string and get “something” to evaluate the formula “dynamically”
– other is to use various methods to iterate through the calculation.

Here are a couple I came up with:

SQL> select xmlquery((listagg(x,' + ' ) within group (order by x)) returning content).getnumberval()
 tot
  2  from (select rownum x
  3        from   dual 
  4        connect by rownum = 1;

       TOT
----------
      5050

SQL> with xyz (x,y) as
  2   (select 1 x, 1 y from dual
  3    union all
  4    select x+1       as x
  5    ,      y + (x+1) as y
  6    from   xyz
  7    where  x  select y as tot
  2  from   dual
  3  model  
  4  dimension by (0 x)
  5  measures     (0 y)
  6  rules     iterate (4294967295) until (iteration_number = 100)
  7               (y[0] = nvl(y[0],1)+iteration_number);

       TOT
----------
      5050

SQL>
Reply
13 07 2011
Dom Brooks (08:35:22) :

oops – made multiple mistakes in my formatting tags.

Reply
13 07 2011
Charles Hooper (09:16:31) :

I think that I was able to fix the formatting tags.

—

A lot of creative solutions so far. As indicated by the solutions provided so far, part of the point of this blog article (and the similar ones that are found on this blog) is not necessarily to provide the most efficient method to solve the problem. Rather, it is to demonstrate different techniques to arrive at the same answer – the most efficient method in any particular solution is not always the most efficient solution when faced with a similar problem. Additionally, part of the point of this blog article is to demonstrate new approaches to solving problems, and those new approaches when applied to completely different problems might be the only visible (possible) angle of attack.

Dom’s two solutions used techniques that I was completely unfamiliar with – I see that I not only need to find some time to dig into the MODEL clause, but also XML related functions.

Reply
13 07 2011
Dom Brooks (10:15:59) :

> I think that I was able to fix the formatting tags
No – There were three – the second and the third have merged.
I’ll attempt a repost.

Doing an evaluation of a string forumla, i.e. generating then evaluating ‘1+2+3…’

SQL> select xmlquery((listagg(x,' + ' ) within group (order by x)) returning content).getnumberval()
 tot
  2  from (select rownum x
  3        from   dual 
  4        connect by rownum <= 100)
  5  where x >= 1;

       TOT
----------
      5050

Recursive With, not something I normally use:

SQL> with xyz (x,y) as
  2   (select 1 x, 1 y from dual
  3    union all
  4    select x+1       as x
  5    ,      y + (x+1) as y
  6    from   xyz
  7    where  x <= 100)
  8  select y
  9  from   xyz
 10  where  x = 100;

         Y
----------
      5050

One way of doing it with model:

SQL> select y
  2  from   dual
  3  model  
  4  dimension by (0 x)
  5  measures     (0 y)
  6  rules     iterate (4294967295) until (iteration_number = 100) -- end_number -1 
  7               (y[0] = nvl(y[0],1)+iteration_number);

         Y
----------
      5050

SQL>

I’m not overly familiar with any of these techniques but these were the ones that immediately sprung to mind as ways to try to do just for fun and not, as you say, with performance in mind.

Reply
13 07 2011
Charles Hooper (14:32:41) :

Dom,

Interesting solutions. I had a bit of trouble generalizing the method using the MODEL clause so that it would not add the numbers 1 through x-1:

select xmlquery((listagg(x,' + ' ) within group (order by x)) returning content).getnumberval() tot  
from (select rownum x  
        from   dual  
      connect by rownum <= 104)  
where x >= 6;  
  
       TOT
----------
      5445

with xyz (x,y) as
  (select 6 x, 6 y from dual
   union all
   select x+1       as x
   ,      y + (x+1) as y
   from   xyz
   where  x <= 104)
 select y
 from   xyz
 where  x = 104;
 
         Y
----------
      5445

select y
 from   dual
 model
 dimension by (0 x)
 measures     (0 y)
 rules     iterate (4294967295) until (iteration_number = 104)
              (y[0] = nvl(y[0],6)+iteration_number);
 
         Y
----------
      5460

Can you see what I did wrong?

Reply
13 07 2011
Charles Hooper (11:22:29) :

Here is a fun method – divide the numbers into two groups, add the results, and count the number of pairs:

VARIABLE X NUMBER
VARIABLE Y NUMBER
EXEC :X := 6
EXEC :Y := 105
 
SELECT DISTINCT
  ((LOW+HIGH)*COUNT(*) OVER ()) S
FROM
  (SELECT
    ROWNUM + (:X - 1) LOW,
    ROWNUM RN
  FROM
    DUAL
  CONNECT BY
    LEVEL <= FLOOR((:Y - :X + 1) / 2)) V1,
  (SELECT
    ROWNUM + (:X - 1) + CEIL((:Y - :X + 1) / 2) HIGH,
    FLOOR((:Y - :X + 1) / 2) - ROWNUM + 1 RN
  FROM
    DUAL
  CONNECT BY
    LEVEL <= FLOOR((:Y - :X + 1) / 2)) V2
WHERE
  V1.RN=V2.RN;
 
         S
----------
      5550

The above works fine until someone does something like the following, and introduces an un-even number of numbers:

EXEC :Y := 104

So, we have to detect that the middle number was excluded. Let’s see, if there is a difference between the CEIL and FLOOR, something is missing:

SELECT 
  (CEIL((:Y - :X + 1) / 2) - FLOOR((:Y - :X + 1) / 2)) M
FROM
  DUAL;
 
         M
----------
         1

So, if we multiply the result of the above by the middle number in between the low and high numbers, we can add that value to the previous result, like this:

SELECT DISTINCT
  ((LOW+HIGH)*COUNT(*) OVER ()) + ((CEIL((:Y - :X + 1) / 2) - FLOOR((:Y - :X + 1) / 2)) * (CEIL((:Y - :X + 1) / 2) + (:X - 1))) S
FROM
  (SELECT
    ROWNUM + (:X - 1) LOW,
    ROWNUM RN
  FROM
    DUAL
  CONNECT BY
    LEVEL <= FLOOR((:Y - :X + 1) / 2)) V1,
  (SELECT
    ROWNUM + (:X - 1) + CEIL((:Y - :X + 1) / 2) HIGH,
    FLOOR((:Y - :X + 1) / 2) - ROWNUM + 1 RN
  FROM
    DUAL
  CONNECT BY
    LEVEL <= FLOOR((:Y - :X + 1) / 2)) V2
WHERE
  V1.RN=V2.RN;
 
         S
----------
      5445
Reply
13 07 2011
Mark W. Farnham (11:49:39) :

If you notice that the sum of the first and last numbers of a sequential list of integers is the same as the sum of the second and next to last number, and that this continues until either all the numbers are paired or if you have an odd number the unpaired number is exactly one-half of all the sums, then you have observed one of the derivations of the formula
(x+y)((y-x+1)/2)
and it doesn’t matter whether the list is an even or an odd number of integers. If both the end points are even or odd, the sum will be even, so one half the sum is still an integer, so no fractional parts, floors, or ceilings are needed. If one end point is even and the other is odd, you have have an integer number of pairs, so it doesn’t matter that the sum is odd.

Reply
13 07 2011
Charles Hooper (13:36:32) :

Mark,

Well stated.

I hid a similar answer in the article, but you explained the concept quite a bit better than I did. 🙂 Roughly half way through the string of – characters at the bottom of this article is an odd blank area created by white text on a white background. If you highlight that area of the article, it should be possible to read my explanation for an immediate answer to the problem. It is a bit reassuring to see that someone else independently arrived at the same solution.

—

With a problem like the one posed in this article, it is possible to think through the problem using logic, play what-if games if there are an even or odd number of elements, or something in between those extremes. I am a little surpised that no one has of yet showed a simple PL/SQL FOR loop.

Reply
13 07 2011
Enrique Aviles (14:15:15) :

Why do it in PL/SQL when you can do it with a single SQL? 🙂

Reply
13 07 2011
Radoslav Golian (14:29:35) :

because PL/SQL (without SQL) is faster 😉

Reply
13 07 2011
jgarry (15:22:47) :

As long as you don’t get tripped up by those darn context switches…

Reply
14 07 2011
Charles Hooper (13:57:31) :

Enrique, Radoslav, Joel good points.

I was actually thinking something similar to what Enrique posted when I added the comment about a simple PL/SQL loop – it probably is not a good idea from a performance perspective to create a PL/SQL function to find the sum of the numbers from 1 to 100 (or x to y) and then return that value in a SQL statement. As Joel mentioned, the performance issues due to the unnecessary context switches can be problematic.

It might not have been 100% clear, but this blog post was looking for solutions to the problem that used Oracle Database to help find the answer to the problem. This time there was no restriction stating that the answer had to be retrieved with a SQL select statement. If you encountered the problem of having to calculate the sum of the numbers between x and y, and were in the middle of programming a PL/SQL function, it is more efficient to find the answer using just a PL/SQL FOR loop (or better yet just calculate the answer using the formulas provided in the comments) than it would be to incur a context switch and execute a SQL statement to calculate the answer. I was a bit surprised when I saw Radoslav’s comment above – yet he has a valid point that if the answer is needed as part of a PL/SQL routine, calculating the answer in that routine is more efficient.

Technically, the question posed by this blog article also did not restrict the use of Java to help calculate the answer, so there might be a couple of additional solutions.

Reply
13 07 2011
Radoslav Golian (15:42:15) :

Optimal solution is to find a closed form for that sum and use it as an algorithm..
Finding a closed form for that easy sum is trivial (http://www.jimloy.com/algebra/gauss.htm)

sum{i=x..y} (i) = x + (x + 1) + (x + 2) + .. + (y - 2) + (y - 1) + y = (x + y) + (x + 1 + y - 1) + (x + 2 + y - 2) .... =  (x + y) * ((y - x + 1)) / 2 

so the best solution is:

var x number;
var y number;
var result number;

exec :X  := &x;
exec :y := &y;

begin
   :result := (:X + :y) * (:y - :X  + 1) / 2;
end;

any SQL statement would be slower..

(edit CH: fixed the scrambled code by replacing x with X in the code section)

Reply
13 07 2011
Radoslav Golian (16:06:39) :

I didn’t notice that Mark was faster than me 🙂

Reply
10 08 2011
Gary Colbran (07:40:27) :

What’s wrong with this ?

select (max(n)+min(n))/2*count(n) from (select level n from dual connect by level < 99);

Should work for any starting number, amount of numbers or increment.

select (max(n)+min(n))/2*count(n) from (select (level+x)*i from dual connect by level < y);

Reply
10 08 2011
Charles Hooper (09:56:57) :

Gary,

I appologize in advance if I am misunderstanding your comment – I think that you are asking how to fix the second SQL statement that you posted.

In the blog article, the following formula appeared in white letters (almost invisible):

(max - min + 1) / 2 * (min + max)

That formula is logically equivalent to this one:

(max + min) / 2 * (max - min + 1)

And the above formula is logically equivalent to the first SQL statement that you provided.

My sample SQL statement:

SELECT   (105 - 6 + 1) /2 * (6 + 105) FROM   DUAL;

Your SQL statement with the same input numbers:

SELECT (105 + 6) / 2 * 100 FROM DUAL;

A minor adjustment to your second SQL statement:

SELECT
  (MAX(N) + MIN(N)) / 2 * COUNT(N) S
FROM
  (SELECT
    LEVEL + 5 N
  FROM
    DUAL
  CONNECT BY
    LEVEL<=((105 - 6) + 1));
 
         S
----------
      5550
Reply

Leave a reply to Raj Cancel reply