SPOJ 1786. In Danger

Task statement

http://www.spoj.com/problems/DANGER/

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. 

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)

DOWNLOAD THE FULL SOURCE CODE