# Switch Game Editorial

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

CAKEWALK

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