📅Day 7 : March 26,2022
Problems solved today :
- Rearrange positive and negative numbers in O(n) time and O(1) extra space
*Tried many approaches but this made a lot of sense to me.
1) sum all the elements from start: prefix sum
2)store prefix sum inside dictionary
* if prefixsum not in dictionary: dict[prefixsum]=1
* else : increase the dictionary[key] +=1
3)Now check for K-prefixsum in dict , if exist increase your count.
Factorial of Very large number
- Couldn't find any linear solution. 5 OPTIONS: a)iterative approach : fact = fact*i b)Recursive : n or n*fact(n-1) c)Math factorial function d)lgamma library function e)Ramanujan's factorial approximation
- a)HashMap should be the best approach(lookup in linear time) OR b)for arr1 in arr2: count +=1 , if(count = len(arr2): Pass.
229.Majority Element II
Finally starting to get in flow and actually thinking about the problem not the code.
Top comments (0)