Explanation using prime factorization


  • 0
    E

    The number of times bulb i is toggled is the number of divisors of i. Let us count the divisors of i.

    Let p1e1 * p2e2 ... * pnen be the prime factorization of i. Since the prime factorization of any divisor d of i will be contained in that of i, we can count the number of unique prime factorizations that are contained in i. For each prime p, there are e+1 choices for the number of times p appears in d (i.e. 0, 1... e). Thus, there are (e1+1) (e2+1) ... (en +1) unique prime factorizations which are a subset of i's factorization, each corresponding to a unique divisor.

    For example, 24=(23)(31). Each divisor can have 0,1,2,3 factors of 2, and 0, 1 factors of 3. The exponents are 3, 1, so there are (3+1)(1+1) = 8 divisors: [1,2,3,4,6,8,12,24]

    Each bulb will be toggled once for each of its divisors, and will remain on if toggled an odd number of times. So we need to count those numbers with an odd number of divisors.

    Using our formula above, a number has an odd number of divisors iff all of the factors in (e1+1)(e2+1)...(en+1) are odd. This means that all of the exponents e1, e2 ... en must be even in order for bulb i to remain on.

    Thus we are looking for numbers which can be expressed as:

    p1(2e1) * p2(2e2) ... pn(2en)

    Factoring out the 2 from the exponents, we get:

    (p1e1 * ... pnen)2

    Thus, bulb i will remain on iff it can be expressed as a (perfect) square.

    We thus need to count the number of perfect squares <= n. This count is given by floor(sqrt(n))


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.