## The New Order Oracle Coding Challenge 1

31 07 2011

July 31, 2011

Years ago I played a couple of different games with letters, rather than numbers, on dice – attempting to form words from the letters displayed on top of the dice.  I was not very good with those games, and I recall attempting to create a computer program to help me with the challenge.  The screaming fast 1 MHz CPU and 64KB of memory proved to be no match for the words listed in the paper-bound dictionary sitting on the shelf.  Computers are significantly faster now, with wide-spread access to Internet based word lists, so it probably would not be much of a challenge today to build a solution for one of those dice letter games.

Finding different combinations with number digits is a bit easier than working with letters – we are able to use math rules to determine if the specified conditions are met rather than a dictionary.  We will start with an easy problem that I found on the web, but I will keep the source of that problem a secret for now.  Consider the number 989,901.  If we write the digits in that number from right to left, we obtain the new number 109,989.  What is special about that new number?  The number is evenly divisible by 3 and 9, but more interesting is that the new number divides evenly into the original number (989,901).

With the help of Oracle Database, find all of the numbers from 1 to 1,000,000 where the digits in the number when listed from left to right are evenly divisible by those same digits listed from right to left.  The numbers that end with 0 are a special case, reversing the order of the digits in those numbers will result in the 0 digit effectively disappearing – as such, exclude any number that ends with 0 from being tested.

There are several methods to swap the order of the digits in the number.  Would you use a different method to test all of the numbers between 1 and 10,000, or to test all of the numbers up to 10,000,000?

Might it work to store the numbers in a reverse key index, and then dump the resulting index values – is that the fourth method to switch the order of the digits?  😉

### 16 responses

31 07 2011
```select n
from
(select level n from dual connect by level <= 10000000)
where mod(n,to_number(reverse(to_char(n)))) = 0
and mod(n,10) <> 0;
```
31 07 2011

The undocumented REVERSE function:

That is a great way to start the possible solutions for this particular problem.

31 07 2011

Sorry, couldn’t help myself. I actually think numbers with trailing zero’s are more interesting than numbers that write the same way backwards and forwards (e.g., 414, 5225, etc…)

31 07 2011

Dominic,

I was 99% certain that a solution with the REVERSE function would not appear before the third or fourth unique solution. The solution that I put together before finalizing this blog article is this one:

```SELECT
N,
RN
FROM
(SELECT
ROWNUM N,
TO_NUMBER(REVERSE(TO_CHAR(ROWNUM))) RN
FROM
DUAL
CONNECT BY
LEVEL<=1000000)
WHERE
MOD(N,RN)=0
AND N <>RN
AND SUBSTR(TO_CHAR(N),-1)<>'0';
```

The above solution is similar to your solution, except for the way that I checked to see if the last digit is a zero.

Without the last digit check it appears that 1,548 numbers match the criteria when testing the numbers up to 1,000,000, but with the check there are 6 numbers. How about when checking the numbers up to 10,000,000 – zero rows returned: 😉

```SQL> SELECT
2    N,
3    RN
4  FROM
5  (SELECT
6    ROWNUM N,
7    TO_NUMBER(REVERSE(TO_CHAR(ROWNUM))) RN
8  FROM
9    DUAL
10  CONNECT BY
11    LEVEL<=10000000)
12  WHERE
13    MOD(N,RN)=0
14    AND N<>RN
15    AND SUBSTR(TO_CHAR(N),-1)<>'0';
ERROR:
ORA-30009: Not enough memory for CONNECT BY operation

no rows selected
```
31 07 2011

Did you check the divisor in each case ? Only 4 or 9.

```  1  SELECT
2    N,
3    RN,
4    n/rn div
5  FROM
6    (SELECT
7      ROWNUM N,
8      TO_NUMBER(REVERSE(TO_CHAR(ROWNUM))) RN
9    FROM
10      DUAL
11    CONNECT BY
12      LEVEL<=1000000)
13    WHERE
14      MOD(N,RN)=0
15      AND N <> RN
16*     AND SUBSTR(TO_CHAR(N),-1)'0'
SQL> /

N         RN        DIV
---------- ---------- ----------
8712       2178          4
9801       1089          9
87912      21978          4
98901      10989          9
879912     219978          4
989901     109989          9

6 rows selected.
```
31 07 2011

Assuming we have a pattern here, it should go on forever I assume ?

```SQL> select 8799912/2199978 from dual;

8799912/2199978
---------------
4

SQL> select 87999912/21999978 from dual;

87999912/21999978
-----------------
4

SQL> select 879999912/219999978 from dual;

879999912/219999978
-------------------
4

SQL> select 9801/1089 from dual;

9801/1089
----------
9

SQL> select 98901/10989 from dual;

98901/10989
-----------
9

SQL> select 989901/109989 from dual;

989901/109989
-------------
9

SQL> select 9899901/1099989 from dual;

9899901/1099989
---------------
9
```
31 07 2011

Gary,

That is an interesting observation – I did not see the pattern until you pointed it out.

```SELECT
N,
RN,
N/RN DIV
FROM
(SELECT
FROM
DUAL
CONNECT BY
LEVEL<=16);

N                   RN        DIV
-------------------- -------------------- ----------
9801                 1089          9
98901                10989          9
989901               109989          9
9899901              1099989          9
98999901             10999989          9
989999901            109999989          9
9899999901           1099999989          9
98999999901          10999999989          9
989999999901         109999999989          9
9899999999901        1099999999989          9
98999999999901       10999999999989          9
989999999999901      109999999999989          9
9899999999999901     1099999999999989          9
98999999999999901    10999999999999989          9
989999999999999901   109999999999999989          9
9899999999999999901  1099999999999999989          9

16 rows selected.
```
```SELECT
N,
RN,
N/RN DIV
FROM
(SELECT
FROM
DUAL
CONNECT BY
LEVEL<=16);

N                   RN        DIV
-------------------- -------------------- ----------
8712                 2178          4
87912                21978          4
879912               219978          4
8799912              2199978          4
87999912             21999978          4
879999912            219999978          4
8799999912           2199999978          4
87999999912          21999999978          4
879999999912         219999999978          4
8799999999912        2199999999978          4
87999999999912       21999999999978          4
879999999999912      219999999999978          4
8799999999999912     2199999999999978          4
87999999999999912    21999999999999978          4
879999999999999912   219999999999999978          4
8799999999999999912  2199999999999999978          4

16 rows selected.
```
1 08 2011

Going back to the inefficient ways to do this, how about the following (requires 11gR2):

```select n, rev, n/rev
from (
select listagg(s, '') within group (order by l) rev, n
from (
select substr(to_char(d.n), -l.n, 1) s, d.n n, l.n l
from (select rownum n, length(rownum) len
from   dual d
connect by level <= :value) d,
(select rownum n
from   dual
connect by level <= length(:value)) l
where l.n <= d.len
and   mod(d.n, 10) <> 0
)
group  by n
)
where floor(n/rev) = ceil(n/rev)
and   n <> rev;
```

This makes a custom reverse function by generating a row for each digit in a number. Work backwards through the digits in the number (using negative numbers in the substr). Then combine back together using listagg.

You could use a positive number in the substr and order descending in the listagg grouping clause as well.

I also hit the “not enough memory” error when trying this with 10,000,000 rows.

1 08 2011

Chris,

Good idea to use the LISTAGG function – the concept behind what you did will be necessary for part 2 of the blog article series.

I have 3 other solutions to this particular problem waiting to be publish, in the hope that someone else will come up with a similar (and likely better) solution – there will certainly be variances between my approach and the one proposed by readers of this blog. For example, the following is the example that I put together using the LISTAGG function:

Building a solution to handle up to a 10 digit number. The idea in this case is to convert the number to a string (VARCHAR), join the number to a view that counts from 1 up to the number of characters in the string version of the number, and use the SUBSTR function to pull out the digits from the right to the left:

```SELECT
N.N,
C.C,
SUBSTR(N.VN, N.LN - (C.C - 1),1) RN
FROM
(SELECT
ROWNUM N,
TO_CHAR(ROWNUM) VN,
LENGTH(TO_CHAR(ROWNUM)) LN
FROM
DUAL
CONNECT BY
LEVEL<=100) N,
(SELECT
ROWNUM C
FROM
DUAL
CONNECT BY
LEVEL<=10) C
WHERE
C.C<=N.LN;

N  C R
---- -- -
1  1 1
2  1 2
3  1 3
4  1 4
5  1 5
6  1 6
7  1 7
8  1 8
9  1 9
10  1 0
10  2 1
11  1 1
11  2 1
12  1 2
12  2 1
...
99  1 9
99  2 9
100  1 0
100  2 0
100  3 1
```

Next, we use the LISTAGG function that was introduced in 11.2.0.1 to recombine the reverse ordered digits back into a single row:

```SELECT
N.N,
TO_NUMBER(LISTAGG(SUBSTR(N.VN, N.LN - (C.C - 1),1), '') WITHIN GROUP (ORDER BY C.C)) RN
FROM
(SELECT
ROWNUM N,
TO_CHAR(ROWNUM) VN,
LENGTH(TO_CHAR(ROWNUM)) LN
FROM
DUAL
CONNECT BY
LEVEL<=1000) N,
(SELECT
ROWNUM C
FROM
DUAL
CONNECT BY
LEVEL<=10) C
WHERE
C.C<=N.LN
GROUP BY
N.N;

N    RN
----- -----
1     1
2     2
3     3
4     4
5     5
6     6
7     7
8     8
9     9
10     1
11    11
12    21
...
993   399
994   499
995   599
996   699
997   799
998   899
999   999
1000     1
```

The final step performs the specified checks:

```SELECT
N,
RN,
N/RN RESULT
FROM
(SELECT
N.N,
TO_NUMBER(LISTAGG(SUBSTR(N.VN, N.LN - (C.C - 1),1), '') WITHIN GROUP (ORDER BY C.C)) RN
FROM
(SELECT
ROWNUM N,
TO_CHAR(ROWNUM) VN,
LENGTH(TO_CHAR(ROWNUM)) LN
FROM
DUAL
CONNECT BY
LEVEL<=1000000) N,
(SELECT
ROWNUM C
FROM
DUAL
CONNECT BY
LEVEL<=10) C
WHERE
C.C<=N.LN
AND N.N/10 != TRUNC(N.N/10)
GROUP BY
N.N)
WHERE
N/RN = TRUNC(N/RN)
AND N != RN;

N      RN     RESULT
------- ------- ----------
8712    2178          4
9801    1089          9
87912   21978          4
98901   10989          9
879912  219978          4
989901  109989          9
```
1 08 2011

I forgot to mention that it is possible to work around the “not enough memory” error when using CONNECT BY through the use of an intentional Cartesian join. As demonstrated below, checking all numbers up to 10,000,000:

```SELECT
N,
RN
FROM
(SELECT
ROWNUM N,
TO_NUMBER(REVERSE(TO_CHAR(ROWNUM))) RN
FROM
(SELECT
ROWNUM N
FROM
DUAL
CONNECT BY
LEVEL<=100000) V1,
(SELECT
ROWNUM N
FROM
DUAL
CONNECT BY
LEVEL<=100) V2)
WHERE
MOD(N,RN)=0
AND N <> RN
AND SUBSTR(TO_CHAR(N),-1)<>'0';

N         RN
---------- ----------
8712       2178
9801       1089
87912      21978
98901      10989
879912     219978
989901     109989
8799912    2199978
9899901    1099989
```
1 08 2011

If you did not know about the undocumented REVERSE function and were running a version of Oracle Database prior to 11.2.0.1, how might you solve this sort of problem?

If you you know that the largest number will have 10 digits, you could do something like the following:

```SELECT
N,
RN
FROM
(SELECT
N,
TO_NUMBER(SUBSTR(VN,10,1)||SUBSTR(VN,9,1)||SUBSTR(VN,8,1)||SUBSTR(VN,7,1)||SUBSTR(VN,6,1)||SUBSTR(VN,5,1)||SUBSTR(VN,4,1)||SUBSTR(VN,3,1)||SUBSTR(VN,2,1)||SUBSTR(VN,1,1)) RN
FROM
(SELECT
ROWNUM N,
TO_CHAR(ROWNUM) VN,
LENGTH(TO_CHAR(ROWNUM)) LN
FROM
DUAL
CONNECT BY
LEVEL<=1000000) N
WHERE
MOD(N,10) != 0)
WHERE
N != RN
AND MOD(N, RN) = 0;
```

The above approach is probably a bit slow.

Instead, you might build a reverse number function:

```CREATE OR REPLACE FUNCTION REVERSE_NUMBER (LNG_NUMBER IN NUMBER) RETURN NUMBER
IS
STR_NUMBER VARCHAR2(15);
STR_RNUMBER VARCHAR2(15);
LNG_RNUMBER NUMBER;
INT_LENGTH NUMBER;
BEGIN
STR_NUMBER := TRIM(TO_CHAR(LNG_NUMBER));
INT_LENGTH := LENGTH(STR_NUMBER);
FOR I IN 1 .. INT_LENGTH LOOP
STR_RNUMBER := STR_RNUMBER || SUBSTR(STR_NUMBER, INT_LENGTH - I + 1, 1);
END LOOP;
LNG_RNUMBER := TO_NUMBER(STR_RNUMBER);

RETURN LNG_RNUMBER;
END REVERSE_NUMBER;
/
```
```SELECT
N,
RN
FROM
(SELECT
ROWNUM N,
REVERSE_NUMBER(ROWNUM) RN
FROM
DUAL
CONNECT BY
LEVEL<=1000000)
WHERE
N/10 != TRUNC(N/10)
AND N/RN = TRUNC(N/RN)
AND N != RN;
```

Any other solutions?

1 08 2011

Another method – use mathematics to reverse the digits in the numbers – the DECODE and SIGN conbination make certain that we do not accidentally pad additional zeros at the end of the reversed number:

```SELECT
ROWNUM N,
TO_NUMBER(
TO_CHAR(MOD(ROWNUM,10)) ||
TO_CHAR(DECODE(SIGN(ROWNUM-10),-1,'',MOD(TRUNC(ROWNUM/10),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-100),-1,'',MOD(TRUNC(ROWNUM/100),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-1000),-1,'',MOD(TRUNC(ROWNUM/1000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-10000),-1,'',MOD(TRUNC(ROWNUM/10000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-100000),-1,'',MOD(TRUNC(ROWNUM/100000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-1000000),-1,'',MOD(TRUNC(ROWNUM/1000000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-10000000),-1,'',MOD(TRUNC(ROWNUM/10000000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-100000000),-1,'',MOD(TRUNC(ROWNUM/100000000),10)))) RN
FROM
DUAL
CONNECT BY
LEVEL<=1000;

---------- ---------
1         1
2         2
3         3
4         4
5         5
6         6
7         7
8         8
9         9
10         1
11        11
12        21
13        31
...
996       699
997       799
998       899
999       999
1000         1
```

Then slide the above into an inline view to perform the tests:

```SELECT
N,
RN,
N/RN DIV
FROM
(SELECT
ROWNUM N,
TO_NUMBER(
TO_CHAR(MOD(ROWNUM,10)) ||
TO_CHAR(DECODE(SIGN(ROWNUM-10),-1,'',MOD(TRUNC(ROWNUM/10),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-100),-1,'',MOD(TRUNC(ROWNUM/100),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-1000),-1,'',MOD(TRUNC(ROWNUM/1000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-10000),-1,'',MOD(TRUNC(ROWNUM/10000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-100000),-1,'',MOD(TRUNC(ROWNUM/100000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-1000000),-1,'',MOD(TRUNC(ROWNUM/1000000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-10000000),-1,'',MOD(TRUNC(ROWNUM/10000000),10))) ||
TO_CHAR(DECODE(SIGN(ROWNUM-100000000),-1,'',MOD(TRUNC(ROWNUM/100000000),10)))) RN
FROM
DUAL
CONNECT BY
LEVEL<=1000000)
WHERE
N <> RN
AND N/10 <> TRUNC(N/10)
AND N/RN=TRUNC(N/RN)
AND N > RN;
```
1 08 2011

Another example that probably will not work with all NLS settings. DUMP the value of the string version of the number, examine the dump value after the colon (:), and use REGEXP_SUBSTR to pick out the “words” (numbers) from the comma separated list that remains. The final step converts the numbers back into ASCII characters with the CHR function:

```SELECT
N,
TO_NUMBER(
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,10))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,9))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,8))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,7))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,6))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,5))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,4))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,3))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,2))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,1))) RN,
D
FROM
(SELECT
ROWNUM N,
DUMP(TO_CHAR(ROWNUM)) D
FROM
DUAL
CONNECT BY
LEVEL<=1000);

N        RN D
---------- --------- ------------------
1         1 Typ=1 Len=1: 49
2         2 Typ=1 Len=1: 50
3         3 Typ=1 Len=1: 51
4         4 Typ=1 Len=1: 52
5         5 Typ=1 Len=1: 53
6         6 Typ=1 Len=1: 54
7         7 Typ=1 Len=1: 55
8         8 Typ=1 Len=1: 56
9         9 Typ=1 Len=1: 57
10         1 Typ=1 Len=2: 49,48
11        11 Typ=1 Len=2: 49,49
12        21 Typ=1 Len=2: 49,50
13        31 Typ=1 Len=2: 49,51
...
995       599 Typ=1 Len=3: 57,57,53
996       699 Typ=1 Len=3: 57,57,54
997       799 Typ=1 Len=3: 57,57,55
998       899 Typ=1 Len=3: 57,57,56
999       999 Typ=1 Len=3: 57,57,57
1000         1 Typ=1 Len=4: 49,48,48,48
```

Next, we slide the above into an inline view and apply the conditions:

```SELECT
N,
RN,
N/RN DIV
FROM
(SELECT
N,
TO_NUMBER(
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,10))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,9))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,8))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,7))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,6))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,5))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,4))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,3))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,2))||
CHR(REGEXP_SUBSTR(SUBSTR(D,INSTR(D,':')+2),'\w+',1,1))) RN
FROM
(SELECT
ROWNUM N,
DUMP(TO_CHAR(ROWNUM)) D
FROM
DUAL
CONNECT BY
LEVEL<=1000000))
WHERE
N/10 <> TRUNC(N/10)
AND N/RN=TRUNC(N/RN)
AND N > RN;
```

Note the number of times the SUBSTR(D,INSTR(D,’:’)+2) value is calculated – for better performance, that value should have been calculated in the inline view where DUMP(TO_CHAR(ROWNUM)) is performed.

1 08 2011

Here is another example that uses recursion to reverse the order of the digits. On Oracle Database 11.2.0.2, this returns an error if there are more than 3 digits in the number:

```WITH N AS
(SELECT
ROWNUM N,
TO_CHAR(ROWNUM) RN
FROM
DUAL
CONNECT BY
LEVEL <= 1000),
R (N, RN2, TEMP) AS
(SELECT
N.N,
SUBSTR(RN,-1) RN2,
SUBSTR(RN,1,LENGTH(RN)-1) TEMP
FROM
N
UNION ALL
SELECT
R.N,
R.RN2 || SUBSTR(R.TEMP,-1) RN2,
SUBSTR(R.TEMP,1,LENGTH(R.TEMP)-1) TEMP
FROM
R
WHERE
R.TEMP IS NOT NULL)
SELECT
N,
TO_NUMBER(RN2) RN
FROM
R
WHERE
TEMP IS NULL;

N        RN
---------- ---------
1         1
2         2
3         3
4         4
5         5
6         6
7         7
8         8
9         9
10         1
11        11
12        21
13        31
...
987       789
988       889
989       989
990        99
ERROR:
ORA-01489: result of string concatenation is too long
```

The same error is returned if we precreate a table:

```CREATE TABLE T5 AS
SELECT
ROWNUM N,
TO_CHAR(ROWNUM) RN
FROM
DUAL
CONNECT BY
LEVEL <= 1000;

WITH N AS
(SELECT
N,
RN
FROM
T5),
R (N, RN2, TEMP) AS
(SELECT
N.N,
SUBSTR(RN,-1) RN2,
SUBSTR(RN,1,LENGTH(RN)-1) TEMP
FROM
N
UNION ALL
SELECT
R.N,
R.RN2 || SUBSTR(R.TEMP,-1) RN2,
SUBSTR(R.TEMP,1,LENGTH(R.TEMP)-1) TEMP
FROM
R
WHERE
R.TEMP IS NOT NULL)
SELECT
N,
TO_NUMBER(RN2) RN
FROM
R
WHERE
TEMP IS NULL;
```

Trying a 4 digit number:

```WITH
R (N, RN2, TEMP) AS
(SELECT
N.N,
SUBSTR(RN,-1) RN2,
SUBSTR(RN,1,LENGTH(RN)-1) TEMP
FROM
T5 N
WHERE
N=1000
UNION ALL
SELECT
R.N,
R.RN2 || SUBSTR(R.TEMP,-1) RN2,
SUBSTR(R.TEMP,1,LENGTH(R.TEMP)-1) TEMP
FROM
R
WHERE
R.TEMP IS NOT NULL)
SELECT
N,
TO_NUMBER(RN2) RN
FROM
R
WHERE
TEMP IS NULL;
```

Recursion in this case is apparently possible on SQL Server, as found in this SQL Server forum thread:
http://www.sqlservercentral.com/Forums/Topic697178-23-1.aspx

Is there a work-around that allows a recursion approach to work on Oracle Database?

3 08 2011
```SELECT id, rev_id
from
( select rownum id
,to_number(reverse(to_char(rownum))) rev_id
FROM dual CONNECT BY level <= 1000000
)
where mod (id, 10) != 0
and   mod(id, rev_id) = 0
and   id != rev_id
```
3 08 2011

Mohamed,

Very nice solution. What you put together shares some similarities with the solution provided by Dominic Delmolino, and one of the solutions that I posted.

Any thoughts on part 2 of the series?:
https://hoopercharles.wordpress.com/2011/08/02/the-new-order-oracle-coding-challenge-2/