online advertising

Tuesday, December 29, 2015

LeetCode OJ - Bulb Switcher

Problem: 

Please find the problem here.

Solution:

A bulb $ b $ is going to be flipped whenever the current round number $ a $ is a factor of $ b $.
Therefore, a bulb is left on only if it is a perfect square (any other number has even number of factors)

With that, the code is trivial.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/bulb-switcher/

#include "LEET_BULB_SWITCHER.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_BULB_SWITCHER
{
    /*
     * Analysis:
     * For the general mth bulb, it is toggled in the nth round if n is a factor of m
     * For example, the 3 bulb is on after round 1 and off after round 3 and will never turn on again (no matter what n is)
     * That applies for all prime
     * That actually also apply for all composite with even number of factors
     * What number has odd number of factors? Squares
     * So it is really just asking how many squares are there
     */
    class Solution {
    public:
        int bulbSwitch(int n)
        {
            int count = 0;
            int k = 3;
            int s = 1;
            while (n >= s)
            {
                count++;
                s += k;
                k += 2;
            }

            return count;
        }
    };
};

using namespace _LEET_BULB_SWITCHER;

int LEET_BULB_SWITCHER()
{
    Solution solution;
    for (int i = 1; i <= 10; i++)
    {
        cout << solution.bulbSwitch(i) << endl;
    }
    return 0;
}

No comments :

Post a Comment