# PROBLEM LINK: Clever Priest

Author: Rituj Aryan
Tester: Rohit Doshi

EASY-MEDIUM

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