Mountain Peak Sequence
Consider the first three natural numbers 1, 2, 3. These can be arranged in the following ways: 2, 3, 1 and 1, 3, 2. Inboth of these
arrangements, the numbers increase to a certain point and then decrease. A sequence with this property is called a “mountain
peak sequence”.
Given an integer N, write a program to find the remainder of mountain peak arrangements that can be obtained by rearranging the
numbers 1, 2, …, N.
Input Format : One line containing the integer N
Input Constraints : Mod = 10^9 +7 3 ≤ N ≤ 10^9
Output Format : An integer m, giving the remainder of the number of mountain peak arrangements that could be obtained from 1, 2, …, N is divide by Mod
Sample Input :
3
Sample Output :
2
Explanation:
If mountain like sequence are formed using the number then count it.
Understand the logic:
- For input 3,6 combinations can be formed,out of these 2 is a mountain sequence.
- For input 4,24 combinations can be formed,out of these,6 Mountain sequence is formed.
- By analyze,we form pattern,Like 2**N-1 -2.
- So that we need to find exponentiation in optimal way and followed by constraints.
Code logic:
- Function for exponentiation power.
- If N==0 return 1.
- else if N==1 return a.
- else:
- R=power(a,N/2)(Note:Recursive call)
- if even return R*R
- else return R*a*R(here the a is the base number)
- a=2
- N input
- call the function(a,N-1)-2
- Also Include the constraint modulo.
Comments
Post a Comment