tsichevski
BAN USER1. Using binary search find the row which might contain the number given. Gives O(log(n)) complexity.
2. Do same to find the column in the row found
@eugene.yarovoi
> Still not logN
IMHO, it is
You just forgot to mention the browser shall find out the protocol to use first, since the "amason.com" does not contain the protocol prefix like "http:\//".
- tsichevski January 21, 2012The sum of two uniformly distributed numbers is not distributed uniformly. For the range [0:4] the distribution will looks like 1 2 3 4 5 4 3 2 1
- tsichevski January 20, 2012@eugene.yarovoi My questions was: are we given only the arrays which allow such partitioning, or the array contents are arbitrary, and we shall deduce also whether the solution exists. For example, this array cannot be partitioned: {1,2}
- tsichevski January 19, 2012It is not so simple. The result will not be equally distributed over the region. See other answers for discussion.
- tsichevski January 18, 2012Is it supposed the solution does exist?
- tsichevski January 17, 20121. Get a random number R in the range 0.. (2^32).
2. Find the minimal number N such as (2^32) mod N is zero, which is more than or equal to R2 - R1 + 1
3. Get M = R mod N
4. return M mod range
The average execution time is not O(n log k), but rather O(k log k), since not every number has to be put into the heap.
- tsichevski January 15, 20121. Calculate the number of integers in the range 1..n, which are missing in the list as X.
2. Get a truly random number in a range 0..X-1 as I.
3. Use I as index into the an imaginary array of 1..n numbers, skipping all numbers which are missing in the list. The solution is the number at this index.
1. The solution to the subproblem 1 is trivial.
2. The solution to the subproblem 2 is trivial only if the number of different values generated by RND() can be divided by X, as noted in previous answers. The trivial solution for the case when the number of different values generated by RND() can *NOT* be divided by X is to select a maximum subregion of length dividable by X, and call RND() until we get values in this subregion. The problem here is that we have unlimited worst case execution time.
3. The solution to the subproblem 3 is trivial.
Your solution has an unlimited worst case execution time.
- tsichevski January 15, 20121. Select an arbitrary pit as start
2. Iterate through every pit in some direction, for each pit calculate the amount of fuel. Some of these values can be negative.
3. Select the pit with the minimum (most negative) value (or any of such pits). This pit is the one we are looking for.
You can keep only 3 nodes in the max heap, and only two nodes in min heap, thus reaching the O(n) complexity.
- tsichevski January 23, 2012