top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# 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.

Tags:

bottom of page