OraQA

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

Filed under SQL. Follow any responses to this entry through this RSS 2.0 feed.