Last Updated: 7 Jul, 2021
Count of paths
Hard
Asked in company
Given a sequence of N integers: arr0, arr1, arr2, ….. arrN-1 and an integer K
K is divisible by all the array elements, ie: K % arri = 0 for (0 <= i <= N-1).
A directed graph is built using this sequence. A directed edge from the jth to the ith array element exists if j < i and ai is divisible by aj, ie: ai % aj = 0.
Find the count of different paths from 0th element to ith element for 0 <= i <= N-1. As the answer can be very large, return answer modulo 109+7.
Input Format:
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.
The first line contains two integers, 'N' and 'K', where N represents the sequence length.
The next line contains N integers, 'ai' for (0 <= i <= N-1).
Output Format:
Print N integers, where ith element denotes the count of different paths from 1st element to ith element.
Output for each test case will be printed in a separate line,
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 5 * 10^4
1 <= K <= 10^9
1 <= ai <= 10^5
Time limit: 1 sec
Approaches
For each position in range 1 to N-1 we will find all jth positions that satisfy the condition for existence of edge from j to i. And we will store all the edges in form of an an adjency list.
As the input sequence can have duplicate values, so rather than the value at a position, consider position index itself as vertices while storing the graph in form of an adjency-list.
Apply dfs from 0th position and simply increase the count for ith node each time it is visited. Return the final answer for each ith position.
The steps are as follows:
- Build an adjency-list to store edges of the graph.
- Declare a array/vector to store the count of paths. ie: vector<int> VIS
- Initialize all elements in VIS to 0.
- Apply dfs from 0st position.
- Each time ith position is visited, increment VIS[i].
- Our answer is finally stored in VIS vector.
Edge can only exist from j to i if j < i. We don’t need to worry about elements to the right-side of ith position while finding the count of paths from 0th to ith element.
We can simply declare a dp array/vector of size N and initialize dp[0]=1 and the initialize rest elements as 0, ie: dp[i]=0 for (1 ≤ i ≤ N-1). Here dp[i] will denote the count of paths from 0th to ith element.
To calculate the value of dp[i], we need to simply iterate for all positions to the left of ‘i’ and if the element of the sequence is divisible by ith element, we will add its count of paths to dp[i].
Finally return elements of dp[i] as they store the count of different paths for ith element.
The steps are as follows:
- Declare a dp array/vector of size = ‘N’, and initialize all elements equal to 0.
dp[i] denotes the count of paths from 0th to ith element. - Assign dp[1] = 1 (base condition)
- Iterate through elements of the dp array, ie: run a for loop from 1 to N-1.
- Calculate dp[i] using another loop that iterates from 0 to i-1. If the element of the sequence is divisible by ith element of the sequence, then simply add its count to dp[i].
Finally, return the elements of dp[i]
Edge can only exist from j to i if j < i. We don’t need to worry about elements to the right-side of ith position while finding the count of paths from 0th to ith element.
We can simply declare a dp array of size N and initialize dp[0] = 1 and the rest elements equal to 0. Here dp[i] will denote the count of paths from 0th to ith element.
We can only reach ith element from factors of a[i] on the left of the element.
So there is no point in iterating from 0 to i-1 to calculate dp[i], we can simply search for factors of a[i] lying on the left of ith position and add their count to dp[i].
We can simply store the given sequence of elements as an unordered_map, where the key of the map denotes the element, and the value of the map stores the positions of that element. Hence we can use an unordered_map of int and vector if int.
We can now simply iterate through the dp array, to calculate dp[i] we will first find factors of a[i], this can easily be done in sqrt(a[i]). We will then search each factor of a[i] in the unordered_map in O(1), if the elements exist, we will add the count to dp[i] corresponding to all the positions less than i.
The steps are as follows:
- Create unordered_map<int, vector<int> > MP
- Iterate all the elements of sequence and fill up the unorder map using MP[ a[i] ].push_back(i).
- Declare a dp array of size=N, and initialize all elements equal to 0.
dp[i] denotes the count of paths from 1st to ith element. - Assign dp[1]=1 (base condition).
- Iterate through elements of the dp array, ie: run a for loop from 0 to N-1, for each iteration calculate all the factors of a[i].
- Search the factors of a[i] in the unordered_map and add the count to dp[i] for all the factors that are on the left of ith position.
Finally, print all the elements of dp[i]