8
\$\begingroup\$

A class has N student and the class room has N switches (all turned OFF and numbered 1 to N). Each student has an enrollment number assigned from 1 to N. Each student serially (by number) toggles the switches that has a number which is divisible by his/her enrollment number.

Example: Student 1 will turn all the switches ON. Student 2 will turn all even switches OFF. Student N just toggles the Nth switch.

Write a function that takes N as input as returns number of ON switches. sample I/O

Input: 10
Output:3

No upper bound for N is given, but greater the scope, better the code. Shortest and innovative function wins

Improve this question
\$\endgroup\$
7
  • 9
    \$\begingroup\$ I think this is way too easy. Essentially this comes down as: »How short can I make an invocation of a library function«. \$\endgroup\$
    – Joey
    Feb 13, 2011 at 11:06
  • \$\begingroup\$ Well yes its easy when the trick is out.. without the perfect square trick, we cant be sure how different people would approach this problem. \$\endgroup\$
    – Aman ZeeK Verma
    Feb 13, 2011 at 23:10
  • 3
    \$\begingroup\$ This is a fairly well-known problem, I guess. At least I stumbled over it at least two or three times by now, mostly in programming contest contexts. And if you have two ways of approaching the problem with vastly different lengths, then you can be sure everyone will jump at the shorter one as soon as the first one does it. \$\endgroup\$
    – Joey
    Feb 14, 2011 at 9:36
  • \$\begingroup\$ @Joey, Totally agreed.. \$\endgroup\$
    – Aman ZeeK Verma
    Feb 14, 2011 at 9:55
  • 1
    \$\begingroup\$ @proudhaskeller If you look at the timestamps, you will notice that the OP seems to have accepted the first answer before any others were posted. \$\endgroup\$
    – alexia
    Aug 16, 2014 at 21:03

13 Answers 13

Reset to default
16
\$\begingroup\$

Python, 19 characters

f=lambda n:n**.5//1

Perfect squares are the only numbers with an odd number of divisors.

This used to be a 21-character answer:

f=lambda n:int(n**.5)

but since I originally wrote it in 2011, the floor-division // operator was introduced, which can replace the int call.

As a consequence, the answer is now returned as a floating-point number. (But f(10) == 3.0 is still a correct number of lockers!)

Improve this answer
\$\endgroup\$
9
  • 1
    \$\begingroup\$ I verified that this does work. However, I would love to know why this works. \$\endgroup\$
    – Mitch
    Feb 13, 2011 at 2:49
  • \$\begingroup\$ It works because every divisor of a number matches up with a different divisor, so they always come in pairs, producing an even number of divisors. The sole exception is if the number is a perfect square, in which case the square root of the number "pairs" with itself, producing an odd number of divisors. \$\endgroup\$
    – Jerry Coffin
    Feb 13, 2011 at 19:28
  • 1
    \$\begingroup\$ There's a lovely post at dailywtf.com about this problem. \$\endgroup\$
    – st0le
    Feb 14, 2011 at 4:49
  • 2
    \$\begingroup\$ Why is this accepted when all other answers are shorter? \$\endgroup\$
    – J B
    Feb 16, 2011 at 12:53
  • 1
    \$\begingroup\$ @J B : Yes all other answers are shorter than this, The answer was accepted after 5 votes and no other solution by that time. More importantly, this funda could not hv been better! \$\endgroup\$
    – Aman ZeeK Verma
    Feb 17, 2011 at 12:49
11
\$\begingroup\$

dc - 5 chars

[v]sf

Square root in dc is v. Using stdin/stdout takes 3 chars (?vp)

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

J, 9 chars

(Just for a simple example on J)

f=:[:<.%:

floor (<.) of square root (%:)

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ But the correct answer is the floor, not the ceiling. \$\endgroup\$
    – Peter Taylor
    Feb 15, 2011 at 15:58
  • \$\begingroup\$ @Peter: right, "<." is floor actually. :/ Thanks. \$\endgroup\$
    – Eelvex
    Feb 15, 2011 at 16:00
  • 2
    \$\begingroup\$ Why not <.@%:? It also never says it has to be a named function, so that brings you down to 5. \$\endgroup\$
    – ɐɔıʇǝɥʇuʎs
    Aug 10, 2014 at 15:22
  • \$\begingroup\$ @ɐɔıʇǝɥʇuʎs, this is from a time where this was debated (i.e. if J had to use a named verb when the question asked for a function). I don't know what the consensus is now. Also, since OP accepted a 21-char long answer, there is little point in golfing this. \$\endgroup\$
    – Eelvex
    Aug 10, 2014 at 20:43
3
\$\begingroup\$

Haskell - 12

Some text so that my post is long enough.

f=floor.sqrt
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ i like this because of the elegant use of the composition operator :) \$\endgroup\$
    – Paul Fisher
    Sep 8, 2020 at 19:24
2
\$\begingroup\$

TI-BASIC, 3

int(√(Ans

Or in Stuck (invalid, since it's from 2015):

i/)

Or in QWERTY Reverse Polish Notation (valid, from 2009):

@r[

Not an interesting answer, but I think they win, since I can't find a language that has either one-character integer square root or implicitly reads from input and performs the calculation in two bytes.

Improve this answer
\$\endgroup\$
2
+100
\$\begingroup\$

APL (Dyalog Extended), 2 bytes

⌊√

Floor of root of the input.

Try it online!, Verify 50 test cases

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

GS2, 2 bytes

V-

The two instructions are parse number, and integer square root, in order.

The reason this works is that the only switches that are on are perfect squares. Those are the only numbers with an odd number of divisors.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ +1—I spent about an hour looking for the correct language and couldn't find it. However, this language was written after the challenge, so it's technically not valid. \$\endgroup\$
    – lirtosiast
    Oct 1, 2015 at 7:19
  • \$\begingroup\$ Oh, sorry, didn't realize this challenge was so old. \$\endgroup\$
    – recursive
    Oct 1, 2015 at 7:41
1
\$\begingroup\$

05AB1E, 2 bytes

tï

Try it online or verify the first N test cases.

Explanation:

t   # Square-root the (implicit) input-integer
 ï  # Cast it to an integer (a.k.a. floors)
    # (after which the result is output implicitly)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 18 bytes

(int)Math.sqrt(n);

Try it online!

Java (JDK), 133 bytes

boolean[]a=new boolean[n];
int c,i=c=0;
for(;++i<=n;)
for(int j=0;++j<= n;)
a[j-1]=j%i==0?!a[j-1]:a[j-1];
for(boolean b:a)
c=b?++c:c;

Try it online!

Improve this answer
\$\endgroup\$
4
  • 2
    \$\begingroup\$ I'm not sure if answers are allowed to take input from a pre-existing variable, you may want to check the default input/outputs allowed \$\endgroup\$
    – Rydwolf Programs
    Nov 30, 2020 at 18:20
  • \$\begingroup\$ I assumed that "Functions may take input via function arguments" meant that, in java, it would translate into "Method arguments" \$\endgroup\$
    – DMiddendorf
    Nov 30, 2020 at 19:17
  • 1
    \$\begingroup\$ I think what most Java answers do here is use a lambda, like n->(int)Math.sqrt(n);. It's only three extra bytes in most cases. \$\endgroup\$
    – Rydwolf Programs
    Nov 30, 2020 at 19:28
  • 1
    \$\begingroup\$ That would make sense. I haven't messed around with lambda in java but will try to do it in further "golfings" :) \$\endgroup\$
    – DMiddendorf
    Nov 30, 2020 at 19:37
0
\$\begingroup\$

Moonscript 23

Pretty simple and self-explanatory

s=(n)->math.floor(n^.5)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Math++, 6 bytes

_sqrt?

(Filler Text Because 30-char minimum)

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Wren, 23 bytes

Basically square-root and floor.

Fn.new{|x|x.sqrt.floor}

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -p, 9 bytes

$_=0|sqrt

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.