1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ [for each positive number given as a query, print] the count of integral multiples in the given array. What is left-sub array - part with smaller index? Larger index? Are the values guaranteed to be increasing in value? How do you arrive at $O(max \times log(max))$ (preprocessing time)? $\endgroup$ – greybeard Oct 10 at 10:02
  • $\begingroup$ @greybeard The problem is to calculate the number of multiples for each arr[i] while traversing the array from left-right. For Example: arr[i] = {2,6,3} then for a[0] there are zero multiples as there is no left-subarray w.r.t a[0], for a[1] there are zero multiples as there are zero multiples for a[1] from a[0] to a[0], for a[2] there is one multiple in the left-subarray {a[0],a[1]} i.e a[1] = 6. So the answer is [0,0,1] $\endgroup$ – Suraj Sharma Oct 10 at 11:55
  • $\begingroup$ This is not a programming site, so I took the liberty of removing your code. $\endgroup$ – Yuval Filmus Oct 10 at 12:17
  • $\begingroup$ @YuvalFilmus Thanks for editing, appreciate it. Can you tell the answer to the problem, because it's been 24 hrs since I posted the problem and nobody has given any answer. $\endgroup$ – Suraj Sharma Oct 10 at 19:06
  • $\begingroup$ You have to be patient. We don’t work for you. We’re not providing a service. $\endgroup$ – Yuval Filmus Oct 10 at 19:27
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, can you give me a small example, like taking a list of some numbers $a_1,a_2,a_3 \cdots a_n$ then how would you proceed? $\endgroup$ – Suraj Sharma Oct 13 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.