Switch Game Editorial

editorial
,
1

problem - CodeChef: Practical coding for everyone
Author and Editorialist: yawner

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic math

PROBLEM:

There are N kids and N switches that are currently OFF. Kth kid changes the state of every kth switch. After Nth kid changes the state of the kth switch, which switches are ON now?

QUICK EXPLANATION:

the switches that would be ON are the ones numbered with “perfect squares”.

EXPLANATION:

The number of factors determines whether a switch is ON or OFF because that’s the number of kids that interacted with it. So the odd number of factors means it’s ON and an even number of factors means it’s OFF. And the only numbers that have an odd number of factors are perfect squares like 16, 25, 36.

TIME COMPLEXITY:

O(sqrt(n)) per test case

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

#define ll long long int

void solve()
{
    ll n;
    cin >> n;
    for (size_t i = 1; i <= sqrt(n); i++)
    {
        cout << i * i << " ";
    }
    cout << endl;
}

int main()
{
    int t = 0;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
5 Likes