How can I make my algorithm more efficient or Is there a better way to solve the problem

Question

Problem Statement: You are given an array/sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$ and you need to execute q queries on the array and in each query you will take a positive number as an input and find out all the multiples of the number in the given array and print it.

Input:
2 4 9 15 21 20
q1 = 2
q2 = 3
q3 = 5

Output:
3
3
2

To solve this problem I thought of an algorithm which works as explained below:

• Create an array name freq_data[] whose length will be equal to the maximum element of the array, and it stores the count of each and every number occurred in the input array.
  For Example:

    array[] = {2, 4, 9, 15, 21, 20}
    max_element = 21
    freq_data[] = {0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1} 
  

• Create an array name multiples[] whose length will also be equal to maximum element encountered in the array. This array will store all the multiples of the numbers between $[1,\text{maximum value}]$. Using multiples[] array, I can answer the query in $O(1)$ time by printing the value at multiples[q - 1].

• Initialise the multiples[0] = (size of arr[] - 1) because every number in the array is divisible by 1.

• If the query entered is $(\gt \text{maximum value})$ in the array, then the answer will be zero because there will be no element in the array which will be divisible by arr[i] because for the number to be multiple of another, the number should be either equal to or greater than the divisor i.e $(\geq arr[i])$.

• Time Complexity: $O(max \times log(max))$
  Space Complexity: $O(max)$

Now I was wondering what if I changed the question like instead of taking the queries from the user, I am now interested in finding for each arr[i] how many multiples are present in the left-sub array with respect to arr[i].

Formally: You are given a sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$. Write a program to count the number of multiples in $a_0,a_1,a_2,\cdots,a_{j-1}$ where $0 \leq j \lt i$ for each $a[i]$ where $0 \leq i \lt n$.

For Example:

1. Input:
arr[] = {2 6 3}
Output:  
no_of_multiples[] = {0,0,1} // For 2 , 6 there are no multiples present but for 3 there is one multiple present i.e. 6  

2. Input:
arr[] = {16,25,63,12,65,45,23,65,78,99,36,12,36,41,36,2,3}
Output:  
no_of_multiples[] ={0,0,0,0,0,0,1,0,0,0,2,1,0,2,6,9}

To solve the above problem, the algorithm which I designed is basically based on the previous problem solution but rather than updating the freq_data[] at once I will first check how many multiples of the arr[i] is present in the freq_data[] and after finding all the multiples, I will increment the value at ++freq_data[data[i] - 1] and then I will print the freq_data[i] array after processing the whole arraarr[i].

Time Complexity: $O(n \times log(max))$
Space Complexity: $O(max)$

Solution In C Programming

My question is: Is there any better algorithm to solve the second part i.e Write a program to count the number of multiples in $a_0,a_1,a_2,\cdots,a_{j-1}$ where $0 \leq j \lt i$ for each $a[i]$ where $0 \leq i \lt n$.

Edit-1: With reference to @gnasher729 points, there are constraints on the inputs because if the size of the input gets larger the algorithm will not give the right answer:

• $1\leq n \leq 10^5$ Constraint on the length of the sequence
• $1 \leq arr[i] \leq 10^6$ Constraint on the values of the sequence

Answer 1

Your attempt runs into a huge problem with the input [1, 2, $2^{63}$].

Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you.

For this specific problem, I think that for any algorithm you give someone will be able to come up with input that makes it behave badly. So I would try to find what are typical inputs and design a solution for those.

With the given restrictions, if the numbers are unique, I’d probably turn the number into a bit array, so to find all multiples of k only max / k numbers need checking. If k is tiny, check the elements of the original array. If k = 1 return the number of array elements. And cache the results.

For example to count the multiples of 1,234 you’d check if bits 1,234, 2,468, 3,702 etc are set which would be 800 checks or so. If large numbers are allowed the solution would be awful.

Answer 2

I think of divisibility mostly in terms of decomposition into prime factors: to be divisible by a query integer $q$, an integer $a_i$ has to be divisible by at least the same power of each prime in $q$s decomposition.
Divisibility by different primes is independent: I think of this (divisibility of integers from a set that can be preprocessed) as a geometric problem of unlimited dimensions.

I do not see a better/cheaper solution for the second form ("batch problem": multiple queries are known right from start) of your problem than for the form stated at the top of your question (single queries).

---

With the example from the question:

Input canonical representation (exponents of primes in ascending order, trailing zeroes omitted)
 2    1
 4    2
 9    0 2
15    0 1 1
21    0 1 0 1
20    2 0 1
Queries - multiples are lines from Input where no exponent is less than for the current query:
 2    1      2, 4, 20
 3    0 1    15, 21
 5    0 0 1  15, 20

If I wanted to get the count of multiples fast, I'd explore keeping summary information like count of numbers divisible by $2^1, 2^2,$ …
Should work like a charm for powers of primes.
What about divisibility by a compound number, say, 6? Sure there are no more multiples of 6 than the minimum of even numbers and numbers divisible by three, but even given an abundance of both, there doesn't have to be a single multiple of 6.