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].
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
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