I have always been fascinated by the top quality editorials written by the likes of @vijju123 and @ssjgz so I thought I’d try my hand at writing an in-depth editorial / tutorial about a problem I’d solved ( though it might be simple)

This post is mostly intended for those starting out . Feel free to look at the headings and skip directly to the sections that interest you.

**Problem Link**

https://www.codechef.com/OCT19A/problems/MSV

**Problem Statement**

You are given a sequence \ A_1 , A_2 .... A_N and for each valid \ i , the star value of element \ A_i is the number of indices \ j \lt i such that \ A_j is divisible by \ Ai .

**Understanding the sample test case**

Let us take a look at the sample test case provided :

```
1
7
8 1 28 4 2 6 7
```

Let us loop through all \ i and try to find the indices \ j \lt i where \ A_j \% A_i == 0

Let us look at the first index \ i = 1 where \ arr[1] = 8 , there are no \ j \lt i here as this is the first element so it’s star value is \ \underline{0}

Now \ i = 2 and \ arr[2] = 1 , there is one index j such that \ j < i

\ j = 1 , is \ arr[1] = 8 divisible by 1 , yes

so star value for this index is \underline{1}

Now \ i = 3 and \ arr[3] = 28 , there are 2 indices \ j , \ j < i that satisfy \ j < i :

\ j = 1 , is \ arr[1] = 8 divisible by 28 , no

\ j = 2 , is \ arr[2] = 1 divisible by 28 , no

so star value for this index is \underline{0}

Now \ i = 4 , \ arr[4] = 4 , there are 3 indices \ j that satisfy \ j < i :

\ j = 1 , is \ arr[1] = 8 divisible by 4 , yes

\ j = 2 , is \ arr[2] = 1 divisible by 4 , no

\ j = 3 , is \ arr[3] = 28 divisible by 4 , yes

so star value is \underline{2}

Now \ i = 5 , \ arr[5] = 2 , there are 4 indices \ j that satisfy \ j < i :

\ j = 1 , is \ arr[1] = 8 divisible by 2 , yes

\ j = 2 , is \ arr[2] = 1 divisible by 2 , no

\ j = 3 , is \ arr[3] = 28 divisible by 2 , yes

\ j = 4 , is \ arr[4] = 4 divisible by 2 , yes

so star value is \underline{3}

Now \ i = 6 , \ arr[6] = 6 , there are 5 indices \ j that satisfy \ j < i :

\ j = 1 , is \ arr[1] = 8 divisible by 6 , no

\ j = 2 , is \ arr[2] = 1 divisible by 6 , no

\ j = 3 , is \ arr[3] = 28 divisible by 6 , no

\ j = 4 , is \ arr[4] = 4 divisible by 6 , no

\ j = 5 , is \ arr[5] = 2 divisible by 6 , no

so star value is \underline{0}

Now \ i = 7 , \ arr[7] = 7 , there are 6 indices \ j that satisfy \ j < i :

\ j = 1 , is \ arr[1] = 8 divisible by 7 , no

\ j = 2 , is \ arr[2] = 1 divisible by 7 , no

\ j = 3 , is \ arr[3] = 28 divisible by 7 , yes

\ j = 4 , is \ arr[4] = 4 divisible by 7 , no

\ j = 5 , is \ arr[5] = 2 divisible by 7 , no

\ j = 6 , is \ arr[6] = 6 divisible by 7 , no

so star value is \underline{1}

**Initial Observations**

We see that for every index \ i , there are \ i-1 indices before it so we have that many \ j to look at. Now looking at the constraints , an O(\ n^2 ) solution seems to definitely tle so the expected solution has to have something to do with factors of each element

**Brute force**

Even though brute force will definitely give tle , I like to code it to get a feel for the problem and also to have something to compare my actual algorithm with

```
#include <iostream>
using namespace std;
int main() {
int t ;
cin >> t ;
while(t--)
{
int n ;
cin >> n ;
long long int arr[n+1] ;
for(int i=1 ; i<=n ; i++)
cin >> arr[i] ;
int star = 0; //This will compute star value for element at each index
long long int max = -1 ; //This will store max store value
for(int i=1 ; i<=n ; i++) //Processing array element by element
{
star =0 ; //Re-initialising each time :)
for(int j=1 ; j<=i-1 ; j++) // We know there are i-1 possibilities for j from 1.....i-1
{
if(arr[j]%arr[i]==0)
{
star++;
}
}
if(max < star)
max = star ;
}
cout << max << endl;
}
return 0;
}
```

As expected , it gets partial AC : Here

**Optimisations**

Now we need to understand that for every \ i , we are finding all \ j such that \ j < i and we are checking if \ A_j mod A_i == 0 . When can this be true ? Only when \ A_i is a factor of \ A_j .

Let us go back to our example

```
1
7
8 1 28 4 2 6 7
```

Let us have an array \ count which keeps track of how many times we’ve looked at a particular factor

Here , what are the factors of \ arr[1] = 8 ?

Yep , the factors are \ 1 , 2 , 4 , 8

\ count[1] = 1

\ count[2] = 1

\ count[4] = 1

\ count[8] = 1

We always know that the star value of the first element will be \bold{0} as there are no indices \ j < i if \ i =1

Now let’s look at the second element , \ i = 2 , \ arr[2] = 1 , for this element to compute the star value , we need to look at the value in the count array for that particular element , we see that 1 has appeared once before as a factor of elements in range \ [ 1 , i-1] so star value for this element is \bold{1}

After we compute the star value for this element , we need to update the count array with the current element we are seeing so only one is a factor of 1

\ count[1] = 2

\ count[2] = 1

\ count[4] = 1

\ count[8] = 1

Let’s look at \ i = 3 , arr[3] = 28

for computing the star value of this element , we see it’s count array value which is 0 , so

star value for this element is \bold{0}

Factors of 28 are \ 1 , 2 , 4, 7 , 14 , 28

so

\ count[1] = 3

\ count[2] = 2

\ count[4] = 2

\ count[7] = 1

\ count[8] = 1

\ count[14] = 1

\ count[28] = 1

Now \ i = 4 , arr[4] = 4

Star value = \ count[4] = \bold{2}

Factors of 4 are \ 1 , 2 , 4

\ count[1] = 4

\ count[2] = 3

\ count[4] = 3

\ count[7] = 1

\ count[8] = 1

\ count[14] = 1

\ count[28] = 1

Now for \ i = 5 , arr[5] = 2

Star value = \bold{3} which is \ count[2] and so on , try to complete the rest of the tracing

and see the maximum star value

**Summary**

The main idea that follows is that to compute the star value of a particular element , we need to look at how many times this element occurs as a factor in the range \ [1 , index-1] because in this question for every \ i we find \ j such that \ j < i and we check if \ A_j \% A_i == 0

All \ j < i is basically \ j = [1 , 2 .... i-1] . For any \ A_i the star value is the count of elements in the range \ [1, ... i-1] which are divisible by \ A_i which reduces the problem to just finding count of factors as when we are at index \ i , we have already looked at \ i-1 elements

**Count of factors in \sqrt{n} ** :

For any \ n if ,

\ a \times b = n

Then ,

\ b = n / a

Let us take \ n = 10 , \sqrt{10} \approx 3

\ 1 \times 10 = 10

\ 2 \times 5 = 10

\ 5 \times 2 = 10

\ 10 \times 1 = 10

As we see , it repeats after a certain point .

(and also observe that \sqrt{n} \times \sqrt{n} )

Basically to enumerate all factors we , Run a loop \ i => 1 .... \sqrt{n}

if \ n \% i == 0 , then \ i is a factor of \ n , so print \ i , what else do we know ?

\ n /i is also a factor so we print \ n/i if \ n/i != i , now for those wondering why the condition is present , take the case of perfect square like \ 25 , when \ i = 5 , \ n/i also is 5 and we do not want duplicates

**You made it**

Link to AC Submission : Here

I know that this is definitely not the best editorial you’ve seen but please do let me know how you found it , any corrections or clarifications and whether I should do more of these , keep in mind I’m very much a beginner

Thank You