Time limit exceeded, how to improve?


  • 0
    J

    Any suggestions on improving the code? Works well before it collapses (exceeds time limit) at 7000000 as input for testcases. Thx for suggestions!

        public class Solution {
            public int bulbSwitch(int n) {
            int[] bulb = new int[n];
            
            for (int i = 1; i <= n; i++) {
                // n rounds of switches going on
                switchB (i, bulb);
            }
            
            return (countOn (bulb));
        }
        
        public void switchB (int round, int[] bulb) {
            int cur = -1;
            
            do {
                cur += round;
                
                if (cur > bulb.length - 1) {
                    break;
                }
                
                switchSingle (cur, bulb);
            }
            while (cur < bulb.length - 1);
        }
        
        public void switchSingle (int cur, int[] bulb) {
            if (bulb[cur] == 1) {
                bulb[cur] = 0;
            }
            else {
                bulb[cur] = 1;
            }
        }
        
        public int countOn (int[] bulb) {
            int count = 0;
            
            for (int j = 0; j < bulb.length; j++) {
                if (bulb[j] == 1) {
                    count++;
                } 
            }
            
            return count;
        }
    }

  • 0
    N

    try to think about some other algorithm, this is brute-force and a way too slow


  • 0
    H

    This problem has an O(1) solution assuming math library gives us results in O(1) times. Work for few n values on paper and see a pattern forming.


Log in to reply
 

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