Consider the first three natural numbers 1, 2, 3. These can be arranged in the following ways: 2, 3, 1 and 1, 3, 2. In both 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.
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.
Constraints:
Mod = 10^9 + 7
N <= 10^9
Example 1
Input:
3
Output:
2
Explanation:
There are two such arrangements: 1, 3, 2 and 2, 3, 1.
Example 2
Input:
4
Output:
6
Explanation:
The six arrangements are (1, 2, 4, 3), (1,3,4,2), (1,4,3,2), (2,3,4,1), (2,4,3,1), (3,4,2,1)
Solution: In C++
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int min(int a,int b)
{
return a>b?a:b;
}
int bino(int n,int r,int p)
{
vector<int>C(r+1,0);
C[0]=1;
for(int i=1;i<=n;i++)
for(int j=min(i,r);j>0;j--)
C[j]=(C[j] + C[j-1])%p;
return C[r];
}
int main()
{
int N, m=0;
int mod = 1000000007;
cin>>N;
for(int i=1;i<N-1;i++)
m+=bino(N-1,i,mod);
cout<<(m%mod);
return 0;
}Solution: In Java
import java.math.BigInteger;
import java.util.Scanner;
class MountainPeakSequence {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
if (N>2) {
BigInteger two = new BigInteger("2");
BigInteger modulo = new BigInteger("1000000007");
System.out.println(two.modPow(BigInteger.valueOf(N-1), modulo).subtract(two.mod(modulo)).mod(modulo));
}
else
System.out.println("O");
s.close();
}
}Solution: In Python 3
from itertools import permutations
N = int(input())
numbers = list(range(1,N+1))
count = 0
perm = list(permutations(numbers))
for i in range(len(perm)):
result = False
for x in range(0, len(perm[i])-1):
if perm[i][x+1] > perm[i][x]:
result = True
else:
break
if result:
for index in range(x, len(perm[i])-1):
if (perm[i][index+1] < perm[i][index]):
result = True
else:
result = False
break
if result:
count = count + 1
print(count)Also Checkout