Find a point in an array where sum of left side array members(wrt to that point) and right side(wrt to that point) are equal..in other words equilibrium point.
SL[i] = sum of numbers from 0 to i (i.e. running sum from left) SR[i] = sum of numbers from n-1 to n-i-1 (i.e. running sum from right) You can build the above two SR,SL in O(n) by doing simple scans from left and right respectively. Now again do another O(n) check to see if there is an x such that SL[x] = SR[n-x-1].
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given "25525511135" , return ["255.255.11.135", "255.255.111.35"] . (Order does not matter)
I want to play a game on a circular table; the rules of which are something like this. (i) I will declare how many people are there initially which is say n. (ii) I will declare the starting position (iiI) I will declare k, which is the person i will keep killing till there is one survival. Eg:: if n =6 and k=3 i will first kill 3rd person then 6th person and so on finally 1st will survive. Now since you are the intelligent among the lot so i want you to come up with a formula which given k and n can help you figuring out a seat for yourself so that you will survive.
SL[i] = sum of numbers from 0 to i (i.e. running sum from left)
ReplyDeleteSR[i] = sum of numbers from n-1 to n-i-1 (i.e. running sum from right)
You can build the above two SR,SL in O(n) by doing simple scans from left and right respectively.
Now again do another O(n) check to see if there is an x such that SL[x] = SR[n-x-1].
@Wrick so for every i ,you will find out SL[i] and SR[i] which is o(n) so overall it will take o(n^2).we need less than that.
ReplyDelete