We are following b users and have limit of 2 * a + 100 users so we can follow 2 * a + 100 - b more users.

Time O(1) | Space O(1)

Code

Since constraints are small, we can iterate from 2 to 1000 and find which number has most GCD-ness.

Time O(n * 1000) | Space O(1)

Code

Optimization — We can also reduce time complexity to O( n * log(max(a)) ) by finding prime factorization of numbers in log(a[i]).

Length of number can be atmost 18 we can use bitmasks to try out all combinations of numbers and take the one in which we remove minimum numbers.

Time O( n * 2 ^ n) | Space O(1) where n is length of number

Code

Optimization — If sum % 3 == 0, answer will be 0. If sum % 3 == 1, we need to remove digits which have % 3 equals (1) or (2, 2). You can find cases for sum % 3 == 2. So this can also be done in O(n).

For each index i, keep track of cumulative sum and also maximum positive value encountered so far. Then answer will be max of current position + maximum positive distance you can travel.

Time O(n) | Space (n)

Code

For every bulb, find the nearest blocked cells in all for directions(left, right, up and down). From that you will know how many cells that bulb will lit up in both directions(horizontally and vertically). Finding those lit cells will be slow if you do it by brute force. Instead you could mark the those start and end for both directions. And after marking it for all bulbs, you can check if that cell is lit by any of the bulbs. If yes then add it to answer.

Time O( n * m ) | Space O ( n * m )

Code