# PROBLEM LINK: Clever Priest

* Author:* Rituj Aryan

*Rohit Doshi*

**Tester:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Math

# PROBLEM:

Given a binary string of length N with all bits 0, apply N operations on it (in any order).

In any operation, choose an integer K (1 \leq K \leq N) and flip all bits present at i_{th} position (1-based indexing) such that i \bmod K = 0. (K should be unique in all operations)

Determine the **number of set bits** in the final string after all N operations.

# HINT

Does order of operations actually matter?

# EXPLANATION:

Observe that no matter in which order you apply N operations, answer will always be the same.

Notice that a bit at position i will be flipped for all K such that i \bmod K = 0.

So, that means if i has *even number of factors*, it will be flipped even times which means it will *always be 0* but for *odd factors* it will become *1*.

So, we need to count all numbers X (1 \leq X \leq N) such that X has odd factors.

A number has odd factors only when it is a **perfect square**.

Therefore, answer is number of perfect squares less than N which is equal to \lfloor \sqrt N \rfloor

NOTE: The **floor function** (\lfloor X \rfloor) takes as input a real number X, and gives as output the greatest integer \leq X

# SOLUTIONS:

## Setter's Solution (CPP)

```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t=1;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>t;
while(t--) {
ll n,ans;
cin>>n;
ans=sqrt(n);
cout<<ans<<"\n";
}
}
```

## Tester's Solution (Python)

```
from math import sqrt
def solve(n):
return int(sqrt(n))
t = int(input())
for _ in range(t):
n = int(input())
ans = solve(n)
print(ans)
```

Feel free to share your approach. In case of any doubt or anything is unclear, please ask it in the comments section. Any suggestions are welcome