City Tour InterviewBit Solution

Problem: City Tour

Problem Description: There are A cities numbered from 1 to A. You have already visited M cities, the indices of which are given in an array B of M integers.

If a city with index i is visited, you can visit either the city with index i-1 (i >= 2) or the city with index i+1 (i < A) if they are not already visited. Eg: if N = 5 and array M consists of [3, 4], then in the first level of moves, you can either visit 2 or 5.

You keep visiting cities in this fashion until all the cities are not visited. Find the number of ways in which you can visit all the cities modulo 10^9+7.

Input Format

The 1st argument given is an integer A, i.e total number of cities.

The 2nd argument given is an integer array B, where B[i] denotes ith city you already visited.

Output Format

Return an Integer X % (1e9 + 7), the number of ways in which you can visit all the cities.

Constraints

1 <= A <= 1000 
1 <= M <= A 
1 <= B[i] <= A

For Example

Input:     A = 5     B = [2, 5] 
Output:    6     

Explanation:     
All possible ways to visit remaining cities are :     
    1. 1 -> 3 -> 4     
    2. 1 -> 4 -> 3     
    3. 3 -> 1 -> 4     
    4. 3 -> 4 -> 1     
    5. 4 -> 1 -> 3     
    6. 4 -> 3 -> 1

Approach

First of all sort array B, then you can see that the elements smaller than the first element of B has only option to be visited. Similarly, this is true for the elements larger than the last element of B. But for the elements that are enclosed with the ranges have more than one option, like in sample example elements 3, 4 can be visited either from the element 2 or from 5. And elements 1 and 6 have only one option or way you can say.

Let's say the size of B as K.

Now there is a total of A-K unvisited cities. We can visit them in (A-K)! ways.

But we can not visit cities between a_i and a_i+1 in all possible ways for all i’s. We have counted all permutations in (A-K)!. So, we need to divide it with (X_i)! for all i’s. Here X-i is the difference between a_i & a_i+1.

This will lead to the expression (A-K)!/(X_0! * X_1! * … *X_k!).

And as we have discussed above in para 1, we have to multiply 2^(X_1 -1 + X_2 - 1 + X_3 - 1 + … + X_(k-1)-1) to the answer because each time we have two options in the range.

Time & Space Complexity

Time Complexity: O(NlogM)

- N is the size of array B and log M is due to the power function.

Space Complexity: O(N)

- To store factorials up to A.

Solution: