Count of paths

Hard
0/120
Average time to solve is 50m
profile
Contributed by
3 upvotes
Asked in company
Directi

Problem statement

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.

 

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6 60
1 2 3 4 5 6
1 10
5
Sample Output 1:
1 1 1 2 1 3 
1
Explanation of sample input 1:
For test case 1:
There is exactly one path to reach 2: 1->2
There is exactly one path to reach 3: 1->3
There are two paths to reach 4: 1->4 and 1->2->4
There is exactly one path to reach 5: 1->5
There are three paths to reach 6: 1->6, 1->2->6 and 1->3->6

For test case 2:
There is only one element, therefore output will be 1.
Sample Input 2:
1
7 120
2 3 4 8 5 6 10
Sample Output 2:
1 0 1 2 0 1 1
Hint

The graph formed will be a Directed Acyclic Graph.

Approaches (3)
dfs on DAG

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:

  1. Build an adjency-list to store edges of the graph.
  2. Declare a array/vector to store the count of paths. ie: vector<int> VIS
  3. Initialize all elements in VIS to 0.
  4. Apply dfs from 0st position.
  5. Each time ith position is visited, increment VIS[i].
  6. Our answer is finally stored in VIS vector.
Time Complexity

O(2N)  where ‘N’ is the length of the sequence given.

In the worst case, when all the elements in input sequence are same, the count of path to ith node will be 2i.
This means we will be incrementing each ith node 2i times, this results in exponential time complexity.
Hence it will cause TLE.

Space Complexity

O(N2) where ‘N’ is the length of the sequence given.


For a very dense graph, there can be ~N2 edges, therefore the space complexity to store the graph in form of an adjacency list is O(N2).

Code Solution
(100% EXP penalty)
Count of paths
Full screen
Console