PROBLEM LINK:
Author: Divyesh Savaliya
Editorialist: Divyesh Savaliya
DIFFICULTY:
Medium
PREREQUISITES:
Math
PROBLEM:
Define the problem in another way.
You have N flower pots, each having a unique flower. Pots are arranged in an arbitrary sequence in a row. You rearranges the sequence each day but not two pots should be arranged adjacent to each other which were already adjacent to each other in previous arrangement. How many days you can do this or how many such arrangements are possible ?
EXPLANATION:
Total number of different pairs that we can make are (N 2) = (N x (N-1))/2. At each day, there are total N-1 pairs made up from adjacent pots. So, the pots present in these N-1 pairs must not come adjacent to each other next day. So, total number of possible arrangements or days are nothing but ((N x (N-1)) / 2) / (N-1) = N/2.
Now, you are given N in binary format. So, you have to convert it to decimal excluding last bit (i.e N>>2). And do the modulo at each step of computation. See the author’s solution to understand the implementation.
Time complexity is O(N).
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.