Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
100 people standing in a circle in an order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next (i.e. No. 3). All people do the same until only 1 survives. Which number survives at the last? There are 100 people starting from 1 to 100.

I want to solve this puzzle using SQL without using any other languages. I have already done it using python. But unable to convert it in sql as a lack of knowledge.

I have the logic with me which I have tried in python. Here using with clause I am trying to assign values but unable to take the power of 2 immediately smaller than N and couldn't able to figure it out, how can i accomodate everything in a single sql without using loop.

Logic,

Step 1 : For a given value of N, find the “Power of 2” immediately smaller than N. Let’s call it P
Step 2 : Subtract N from (P-1). Lets call it M, i.e, M = (P-1)- N
Step 3 : Multiply M by 2. i.e M*2
Step 4 : Subtract M*2 from P-1. Let’s call it ans, i.e, ans = (P-1) – (M*2)
So, the person with number “ans” will survive till last.

Your help will be much appreciated.

What I have tried:

<pre lang="SQL">


WITH p(n) AS (
  SELECT 1 from dual
  UNION ALL
    SELECT n+1 FROM t WHERE n < 100
	)
SELECT * FROM t;
with RECURSIVE pow(t)(
select power (t,2) where t<n);
Posted
Updated 27-Nov-22 21:38pm

1 solution

First all the even number dies then left with the odd number only. Then the passing goes on within the odd number in sequence from smaller to larger until one people stands, that is number 73 is the winner.
The solution requires getting the nearest numbers that is the power of 2 which is smaller than total number of soldiers, in this case 64 and subtract it with the given number.
100-64=36.
Now we apply the formula;2n+1 = 2*36 + 1 = 72 + 1 = 73.

CODE--

SELECT (2*(100 - MS) + 1) AS R
FROM (SELECT MAX(t) MS
FROM (SELECT rownum,
(POWER(rownum,2)) AS t,
MOD(rownum,2) AS M
FROM (SELECT 1 FROM dual GROUP BY CUBE(1,2,3,4,5,6,7))
WHERE rownum <= 100)
WHERE M = 0
AND t < 100);

MS --max of squre
M-- Dividend is stored as M
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900