Problem Statement: They give you a matrix / sequence of positive numbers $ a_1, a_2, a_3, cdots, a_n $ and you need to run q
queries in the matrix and in each query will take a positive number as input and discover all the multiples of the number in the given matrix and print.
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 that works as explained below:

Create an array name freq_data()
whose length will be equal to the maximum element of the matrix, and stores the count of each and every number occurred in the input matrix.
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 the maximum element found in the matrix. This matrix will store all multiples of the numbers between $ (1, text {maximum value}) $.

Initialize the multiples(0) = (size of arr()  1)
because each number in the matrix is divisible by 1.

If the query entered is $ ( gt text {maximum value}) $ in the matrix, then the answer will be zero because there will be no element in the matrix that is divisible by arr(i)
because for the number to be a multiple of another, the number must be equal to or greater than the divisor, that is $ ( geq arr (i)) $.

When creating a multiples()
I will be able to answer each query in constant time by printing the value in multiples(q  1)
.

Complexity of time: $ O (max times log (max)) $
Spatial Complexity: $ O (max.) $
Using all these facts, I wrote the code in programming language C as follows:
#include
#include
#include
#include
#include
uint32_t* find_all_multiples(uint32_t(),uint32_t,uint32_t);
int main(void) {
uint32_t n,max_val = 0;
printf("Enter the size of the sequencen");
scanf("%"SCNu32,&n);
uint32_t data(n);
printf("Enter the datan");
for(uint32_t i = 0; i < n; ++i) {
scanf("%"SCNu32,&data(i));
assert(data(i) > 0);
if(data(i) > max_val) {
max_val = data(i);
}
}
uint32_t *const multiples = find_all_multiples(data,n,max_val);
uint32_t query;
printf("Enter the number of queriesn");
scanf("%"SCNu32,&query);
while(query) {
uint32_t num;
scanf("%"SCNu32,&num);
if(num > max_val) {
printf("0n");
} else {
printf("%"PRIu32"n",multiples(num  1));
}
}
free(multiples);
return 0;
}
uint32_t* find_all_multiples(uint32_t data(),uint32_t n,uint32_t max_val) {
uint32_t *const freq_data = calloc(max_val,sizeof(uint32_t));
for(uint32_t i = 0; i < n; ++i) {
++freq_data(data(i)  1);
}
uint32_t *const multiples = calloc(max_val,sizeof(uint32_t));
multiples(0) = n  1;
for(uint32_t i = 2; i <= max_val; ++i) {
for(uint32_t j = i; j <= max_val; (j += i)) {
multiples(i  1) += freq_data(j  1);
}
}
for(uint32_t i = 0; i < max_val; ++i) {
printf("%"PRIu32" ",multiples(i));
}
printf("n");
free(freq_data);
return multiples;
}
Now I was wondering what would happen if I changed the question instead of taking user queries, I am now interested in finding each arr(i)
how many multiples are present in the subleft matrix with respect to arr(i)
and I wrote the code to solve this problem too, but I'm curious to know if I can do better.
For example:
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
The algorithm I designed is basically based on the previous algorithm, but instead of updating the freq_data()
at the same time I will first check how many multiples of arr(i)
is present in the freq_data()
and after finding all the multiples, I will increase the value in ++freq_data(data(i)  1)
You can see the source code below:
#include
#include
#include
#include
#include
#include
struct multiples_array {
uint32_t value;
uint32_t no_of_multiples;
};
typedef struct multiples_array multiples_array_t;
void take_input(multiples_array_t *const,uint32_t);
void generate_multiples(multiples_array_t *const,uint32_t);
const uint32_t find_maximum(multiples_array_t *const,uint32_t);
int main(void) {
uint32_t n;
printf("Enter the size of the arrayn");
scanf("%"SCNu32,&n);
assert(n > 0);
multiples_array_t *const data = calloc(n,sizeof(multiples_array_t));
if(data) {
take_input(data,n);
generate_multiples(data,n);
free(data);
} else {
fprintf(stderr,"Memory not allocated to *data pointer!n");
}
return 0;
}
void take_input(multiples_array_t *const data,uint32_t n) {
for(uint32_t i = 0; i < n; ++i) {
scanf("%"SCNu32,&(data(i).value));
data(i).no_of_multiples = 0;
assert((data(i).value) > 0);
}
}
void generate_multiples(multiples_array_t *const data,uint32_t n) {
uint32_t max_val = find_maximum(data,n);
uint32_t *const freq_data = calloc(max_val,sizeof(uint32_t));
if(freq_data) {
for(uint32_t i = 0; i < n; ++i) {
if((data(i).value) > max_val) {
max_val = data(i).value;
}
if(data(i).value == 1) {
data(i).no_of_multiples = i;
}
else if(data(i).value <= max_val) {
for(uint32_t j = 1; ((data(i).value) * j) <= max_val; ++j) {
(data(i).no_of_multiples) += freq_data(((data(i).value) * j)  1);
}
}
++freq_data((data(i).value)  1);
}
for(uint32_t i = 0; i < n; ++i) {
printf("%"PRIu32" ",(data(i).no_of_multiples));
}
printf("n");
free(freq_data);
} else {
fprintf(stderr,"Memory not allocated to *freq_data pointer!n");
}
}
const uint32_t find_maximum(multiples_array_t *const data,uint32_t n) {
uint32_t max = 0;
for(uint32_t i = 0; i < n; ++i) {
if((data(i).value) > max) {
max = data(i).value;
}
}
return max;
}
Complexity of time: $ O (n times log (max)) $
Spatial Complexity: $ O (max.) $
My question is: is there any better algorithm to solve the second part, that is, to find all the multiples of arr(i)
in the subleft matrix $ forall i $?