OraQA

Oracle Question and Answer


Latest Comments

  • Laurent Schneider:
    if you like a Base64 format, maybe this… select utl_raw.cast_to_varchar 2(...

  • hsafra:
    You need to give more specs for the question: What letter are acceptable? What letters aren’t? Do you...

  • ragunathansd:
    I am not inserting sequence numbers from database. I need to populate the data in a grid. If a user...

  • gamyers:
    “redo log file gets full” That is the nature of a redo log file. It gets full, switched and...

Comments RSS feed


  • Do you have a solution to a problem? Do you have an unanswered question? Login and share it with the Oracle community. More...

Oracle News


Entries RSS feed

Comments RSS feed

How to solve the Impossible Combination Puzzle in SQL

February 5th, 2008 By Frank Zhou

The following is an interesting puzzle posted by Usenet rec-puzzles.org archive:

What is the smallest number of coins that you can’t make a dollar with? i.e., for what N does there not exist a set of N coins adding up to a dollar? It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony),
2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece), etc. It is not possible to make exactly a dollar with 101 coins.

—————————SQL Solution—————–

SELECT MIN (num) Min_Impossible_Combinations
FROM
(SELECT LEVEL num  FROM DUAL CONNECT BY LEVEL <=101
  MINUS
 SELECT
  SUM(TO_NUMBER(SUBSTR(num,
           INSTR(num,',', 1, LEVEL) + 1,
           INSTR(num,',', 1, LEVEL+1) -
           INSTR(num,',', 1, LEVEL) -1))) num
FROM
(SELECT sys_connect_by_path(num,',')||',' num, rownum rn,
        regexp_replace(sys_connect_by_path(str_num,','),'[[:alpha:]]') ||',' AS str_num
FROM
(SELECT str_num, num, to_number(substr(str_num,0,length(str_num)-1)) n,
        substr(str_num,length(str_num)) coin_type
   FROM
(SELECT LEVEL||'A' str_num ,   LEVEL AS num
   FROM dual CONNECT BY LEVEL <=100
 UNION ALL
 SELECT LEVEL*5||'B' str_num,  LEVEL
   FROM dual CONNECT BY LEVEL*5 <=100
 UNION ALL
 SELECT LEVEL*10||'C' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*10 <=100
 UNION ALL
 SELECT LEVEL*25||'D' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*25 <=100
 UNION ALL
 SELECT LEVEL*50||'E' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*50<=100
 UNION ALL
 SELECT LEVEL*100||'F' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*100<=100
 )
)
WHERE
CASE LEVEL
WHEN  1 THEN CASE WHEN n = 100 THEN 1 END
WHEN  2 THEN CASE WHEN n + PRIOR  n =100 THEN 1 END
WHEN  3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n =100 THEN 1 END
ELSE  1 END =1
CONNECT BY PRIOR coin_type < coin_type
AND
CASE LEVEL
WHEN 2 THEN CASE WHEN n + PRIOR n <=100 THEN 1 END
WHEN 3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=100 THEN 1 END
WHEN 4 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <96   THEN 1 END
WHEN 5 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=85  THEN 1 END
ELSE 1 END =1
AND LEVEL <6
)
CONNECT BY PRIOR rn = rn
AND INSTR (str_num,',', 1,LEVEL+1) > 0
AND PRIOR dbms_random.string('p',10) IS NOT NULL
GROUP BY rn
HAVING SUM(TO_NUMBER(SUBSTR(str_num,
           INSTR(str_num,',', 1, LEVEL) + 1,
           INSTR(str_num,',', 1, LEVEL+1) -
           INSTR(str_num,',', 1, LEVEL) -1))) = 100
);

MIN_IMPOSSIBLE_COMBINATIONS
---------------------------
                         77

Elapsed: 00:00:08.06

Leave a Reply

You must be logged in to post a comment.

RSS feed for comments on this question