Josephs problem
Its just a simple pattern that needs to be observed and derived mathematically. :)
the pattern is listed below.
First of all this task requires a very special approach. If the task usually has one input and one output and the constraints are very high, you should understand that the solution is a simple formula or something close to it. I recommend writing a simple brute force solution for the first 1000 , print them one after another and you will easily notice the drill.
Task statement
(pasted)
Its just a simple pattern that needs to be observed and derived mathematically. :)
the pattern is listed below.
For making it clear , you can find the answer for the first 100 elements below.
1---1
2---1
3---3
4---1
5---3
6---5
7---7
8---1
9---3
10---5
11---7
12---9
13---11
14---13
15---15
16---1
17---3
18---5
19---7
20---9
21---11
22---13
23---15
24---17
25---19
26---21
27---23
28---25
29---27
30---29
31---31
32---1
33---3
34---5
35---7
36---9
37---11
38---13
39---15
40---17
41---19
42---21
43---23
44---25
45---27
46---29
47---31
48---33
49---35
50---37
51---39
52---41
53---43
54---45
55---47
56---49
57---51
58---53
59---55
60---57
61---59
62---61
63---63
64---1
65---3
66---5
67---7
68---9
69---11
70---13
71---15
72---17
73---19
74---21
75---23
76---25
77---27
78---29
79---31
80---33
81---35
82---37
83---39
84---41
85---43
86---45
87---47
88---49
89---51
90---53
91---55
92---57
93---59
94---61
95---63
96---65
97---67
98---69
99---71
100---73
Pay a close attention to the numbers which are powers of 2 (2,4,8,16). They are equal to 1, after every power of two , the next answer equals to the previous answer +2.
2^n 1
2^n+1 3
2^n+2 5
2^(n+1) 1
.....
.....
So , the only thing which is left is to take care of the input then find the biggest power of two which is smaller than the given number and calculate.
Here is the formula
answer=1+(n-P)*2; (P is the biggest number which is a power of 2 and is smaller than n)
No comments:
Post a Comment