Count Ways to Travel Cities
Learn this problem
CommvaultOAProblem statement
In a country there are different cities and the cities marked with integer number starting from 1. And now you need to travel in the N cities with some following criteria.
- You need to travel exactly N cities and you can start travelling from any of the cities
- If you visit a city of number n, then the next city number will be more than or equal to 2n
- And you are also given a number K and any city number can't more than K.
Now you are given N and K, need to find how many ways you can travel the cities by keeping in mind the conditions given. And return the answer in module 1000000007 as the answer will be very large.
Function
countWaysToTravelCities(N: int, K: int) → int
Complete the function countWaysToTravelCities in the editor.
countWaysToTravelCities has the following parameters:
N: an integer, the number of cities to travelK: an integer, the maximum city number allowedReturns
int: the number of ways to travel the cities modulo 1000000007
Examples
Example 1
N = 3K = 10return = 20Some of the valid city paths will be -
- 1-2-4
- 1-3-6
- 1-4-8
If the first city is 1, there are 16 valid paths. If the first city is 2, there are 4 valid paths. A larger starting city cannot leave enough room for two subsequent cities, so the total is 20.