Beginner
1. Consecutive Prime Sum2. Alpha Numeric Sorting3. Longest Progressive Sequence4. Divine Divisor5. Forest Fire6. Minimum Distance7. Saving for a rainy day8. Online Communities Even Groups9. Coin Distribution10. Bank Compare11. Counting Rock Samples12. Collecting Candies13. Game Of Primes14. Kth Largest Factor15. Jumble With Numbers16. Philand Coins17. Reverse Gear18. String Rotation19. The Vita Sum20. Mountain Peak Sequence21. LAZY STUDENT22. LOGIC PYRAMID23. Super ASCII String Checker24. Min Product Array25. String Of Brackets26. Exchange Of Digits27. Marathon Winner28. Common Steps29. Swayamvar30. Digit Pairs31. Dole Out Cadbury32. Petrol Pump33. Grooving Monkeys34. Death BattleMountain Peak Sequence
LEVEL:Beginner
Description
Given an integer value 3, consider the first thre 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. When divided by Mod
Input Format
One line containing the integers N
Constraints:
Mod = 10^9 + 7
N <= 10^9
Output Format
An integer m, giving the remainder of the number of moountain peak arrangements that could be obtained from 1,2...........N, is divided by Mod
3
2
4
6
50
949480667
Login to see Discussion
Approach
here let's understand the question , in question it is said that it should be a mountain peak. So the numbers shouldn't be in either increasing or decreasing order
if n=1 answer is 0 answer is 0 as there is no mountain peak (1)
if n=2 answer is 0 as here too there is no mountain peak (1,2)
if n=3 Here there are two chances one we can place 3 in middle of previous combinations which is (1,3,2) and reverse is also possible which is (2,3,1)
if n=4 here we can place place it either before or after 3 or previous combinatin which is (1,4,3,2) or (1,3,4,2) similarly we get (2,4,3,1) and (2,3,4,1) and two more combinations are (1,2,4,3) and (1,4,2,3)
so here we can observe pattern that
from 3 on wards we have no have patterns equal to 2 times of previous one plus 2
it becuase for every previous pattern we can place present number before or after a certain number and 2 more ways to the ascending order of n-1
so our logic will be
for i 1 to n-2 (as there are no combinations for 1 or 2)
answer = (answer *2 ) + 2here let's understand the question , in question it is said that it should be a mountain peak. So the numbers shouldn't be in either increasing or decreasing order
if n=1 answer is 0 answer is 0 as there is no mountain peak (1)
if n=2 answer is 0 as here too there is no mountain peak (1,2)
if n=3 Here there are two chances one we can place 3 in middle of previous combinations which is (1,3,2) and reverse is also possible which is (2,3,1)
if n=4 here we can place place it either before or after 3 or previous combinatin which is (1,4,3,2) or (1,3,4,2) similarly we get (2,4,3,1) and (2,3,4,1) and two more combinations are (1,2,4,3) and (1,4,2,3)
so here we can observe pattern that
from 3 on wards we have a patterns which is present answer equal to 2 times of previous one plus 2
it becuase for every previous pattern we can place present number before or after a certain number and 2 more ways to the ascending order of n-1
so our logic will be
for i 1 to n-2 (as there are no combinations for 1 or 2)
answer = (answer *2 ) + 2
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution