CLPRI - Editorial

editorial
, , , , ,
1

PROBLEM LINK: Clever Priest

Author: Rituj Aryan
Tester: Rohit Doshi

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 :smile: