Buses
You are given a vector of 'N' integers denoting the number of buses that can be boarded from the i-th position. The bus stops only at stops whose number is a multiple of the bus stop number from which the bus originates. You need to find the number of buses originating from each bus stop from 1 to 'N'.

For example:

If 'N' = 4 and the given vector is: [1 3 4 3]. 1 bus can be boarded from the first bus stop which means that 1 bus originates from the first bus stop. 3 buses can be boarded from the second bus stop which means that (3 - 1 = 2) buses originate from the second bus stop. This is because the bus originating from the first stop will stop at the second stop as well. 4 buses can be boarded from the third bus stop which means that (4-1 = 3) buses originate from the third bus stop. This is because the bus originating from the first stop will stop at the third stop as well. 3 buses can be boarded from the fourth bus stop which means that (3-3 = 0) buses originate from the fourth bus stop. This is because the buses originating from the first and second stop will stop at the fourth stop as well. So the final vector would be: [1 2 3 0].

Note:

The given vector uses 1-based indexing.

Input Format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. Then the 'T' test cases follow. The first line of each test case contains a single integer 'N' representing the length of the vector. The second line of each test case contains 'N' space-separated integers denoting the elements of the given vector.

Output Format:

For each test case, print 'N' integers denoting the number of buses originating from each bus stop from 1 to 'N'.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 ≤ T ≤ 50 1 ≤ N ≤ 10^4 1 ≤ Ai ≤ 10^6 Time Limit : 1 sec

Question

Buses

You are given a vector of 'N' integers denoting the number of buses that can be boarded from the i-th position. The bus stops only at stops whose number is a multiple of the bus stop number from which the bus originates. You need to find the number of buses originating from each bus stop from 1 to 'N'.

For example:

If 'N' = 4 and the given vector is: [1 3 4 3].

1 bus can be boarded from the first bus stop which means that 1 bus originates from the first bus stop.

3 buses can be boarded from the second bus stop which means that (3 - 1 = 2) buses originate from the second bus stop. This is because the bus originating from the first stop will stop at the second stop as well.

4 buses can be boarded from the third bus stop which means that (4-1 = 3) buses originate from the third bus stop. This is because the bus originating from the first stop will stop at the third stop as well.

3 buses can be boarded from the fourth bus stop which means that (3-3 = 0) buses originate from the fourth bus stop. This is because the buses originating from the first and second stop will stop at the fourth stop as well.

So the final vector would be: [1 2 3 0].

Note:

The given vector uses 1-based indexing.

Input Format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 
Then the 'T' test cases follow.

The first line of each test case contains a single integer 'N' representing the length of the vector.

The second line of each test case contains 'N' space-separated integers denoting the elements of the given vector.

Output Format:

For each test case, print 'N' integers denoting the number of buses originating from each bus stop from 1 to 'N'.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 10^4
1 ≤ Ai ≤ 10^6

Time Limit : 1 sec

Accepted Answer

Brute Force

Use two nested loops for finding the answer.
Use the outer loop for finding the final solution and the inner loop for subtracting the buses which do not start from that place.
For each bus stop in the inner loop which is a divisor of the outer loop, subtract it from the number of buses in the inner loop.
Go on doing this, till we traverse the whole array/list.

Space Complexity: O(1)Explanation:

O(1)

As there is no extra space required.

Time Complexity: O(n^2)Explanation:

O(N^2) Where N is the size of array/list.

As we are iterating on all the elements of an array/list using two nested loops. Hence the time complexity is O(N^2).

Accepted Answer

Optimal Solution

Use two nested loops for finding the answer.
This time we will only traverse the multiples of the outer loops in the inner loop.
We can do this by multiplying the outer loop by 2 and going on till N, subtracting the number of people in the outer loop(the actual number).
Use the inner loop for finding the final solution and the outer loop for subtracting the buses which do not start from that place.
For each bus stop in the outer loop which is a divisor of the inner loop, subtract it from the number of buses in the inner loop.
Go on doing this, till we traverse the whole vector.

Space Complexity: O(1)Explanation:

O(1)

As there is no extra space required.

Time Complexity: O(nlogn)Explanation:

O(N * logN) Where N is the size of the input array/list ‘ARR’.

As we are running two loops and corresponding to the first loop, the second loop will run N times for the first iteration, N/2 times for the second iteration… hence it is forming a series N/1 + N/2 + N/3 …. which is NlogN. Hence the runtime complexity of this solution is O(N * logN).

Accepted Answer

vector<int> countBuses(vector<int> arr, int n){ arr.insert(arr.begin(), -1); for(int i=1; i<=n; i++) for(int j=i*2; j<=n; j=j+i) arr[j]=arr[j]-arr[i]; arr.erase(arr.begin()); return arr; }

This is C++

Accepted Answer

The language is c++

vector<int> countBuses(vector<int> arr, int n){ arr.insert(arr.begin(), -1); for(int i=1; i<=n; i++) for(int j=i*2; j<=n; j=j+i) arr[j]=arr[j]-arr[i]; arr.erase(arr.begin()); return arr; }

For example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Microsoft Corporation Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Microsoft Corporation Software Developer