ranan.fraer
BAN USERTransform each IP address into a vector of 4 bytes, b1.b2.b3.b4
Step1 : Apply bucket-sort with 256 buckets using b1 as a key. All IP-s with b1 = k are placed into bucket k, for k = 0 to 255. O(n) time complexity.
Step 2: Go over all the buckets that have more than 1 element, and apply another bucket sort using b2 as a key. O(n) time complexity.
Step 3/4 : Apply bucket sort with b3/b4 as a key respectively for all sub-buckets that still have more than 1 element.
Total complexity: O(4*n) = O(n). Worst case is when all the IP addresses are the same, as they will go to the same bucket for each of the steps.
s100banerjee, you're right, my mistake. I take back my comment ...Nice solution!
- ranan.fraer April 06, 2015s100banerjee, I'm afraid that your solution uses O(n) extra memory for the TreeMap occurrence.
- ranan.fraer April 04, 2015Hi, your solution is very elegant, but not scalable ... The total size of the 256 strings = the size of the input strings. And we may expect a lot of input strings, for the probabilities to be statistically significant. It makes more sense to store only the counters, or the probabilities as proposed by the other solutions.
- ranan.fraer March 27, 2015Actually the smallest number divisible by A is A itself; I assume that zero doesn't count. So all we need is to call findBin(A).
- ranan.fraer February 07, 2015I agree, both TLT and LTL are valid answers (using the notation of VK). We have a statement that relates the 1st to 2nd, and a statement that relates the 2nd to 3rd. To derive some contradiction, would require some statement that closes the loop by relating the 1st and the 3rd person.
- ranan.fraer June 05, 2014Here's a helpful math statement that is easy to prove:
A positive integer number N divides by 11 if and only if (the sum of even place digits of N) - (the sum of odd place digits of N) is a multiple of 11.
Examples: 209, 220, 231, ..., 297, 308, 319, 330, 341, ...
In particular:
If (sum of even place digits) == ( sum of odd place digits) then N divides by 11.
Examples: 220, 231, ..., 297, 330, 341
Note how the more strict criterion leaves out numbers like 209, 308, 319, etc.
Now back to our problem. We can prove the following result
If (sum of even place digits) - ( sum of odd place digits) == 1, then we can prove that N mod 11 == 1, i.e. N is a multiple of 11 + 1.
Proof:
Case 1: If the digit at position 0 (last digit) is not 0, then we can subtract 1 from this digit and get a multiple of 11. So N - 1 == 0 mod 11. Examples: 221, 232, 243, ..
Case 2: If the last digit is 0, but the digit at position 2 is not 0. Then we can subtract 1 from this digit and get a a multiple of 11. So N - 100 = 0 mod 11, or N - (99 + 1) = 0 mod 11. Examples: 320, 430, 540, ...
In the general case, at least one of the even place digits is not 0 (since the sum of the even place digits is greater than the sum of odd place digits). If it's the position 2k, then we subtract 1 from that digit, and we get N - 10^2k = 0 mod 1. But 10^2k = 100^k = (99 +1)^k = 1 mod 11.
Finally, the algorithm is to scan all the numbers N in the range [A,B] such that N = 1 mod 11. Once we find the first such N, the next one is found by adding 11. For each N, we check if (sum of even place digits) - ( sum of odd place digits) == 1. This will filter out numbers like, 309, 408, 507, etc. that don't meet the criterion.
Here's a helpful math statement that is easy to prove:
A positive integer number N divides by 11 if and only if (the sum of even place digits of N) - (the sum of odd place digits of N) is a multiple of 11.
Examples: 209, 220, 231, ..., 297, 308, 319, 330, 341, ...
In particular:
If (sum of even place digits) == ( sum of odd place digits) then N divides by 11.
Examples: 220, 231, ..., 297, 330, 341
Note how the more strict criterion leaves out numbers like 209, 308, 319, etc.
Now back to our problem. We can prove the following result
If (sum of even place digits) - ( sum of odd place digits) == 1, then we can prove that N mod 11 == 1, i.e. N is a multiple of 11 + 1.
Proof:
Case 1: If the digit at position 0 (last digit) is not 0, then we can subtract 1 from this digit and get a multiple of 11. So N - 1 == 0 mod 11. Examples: 221, 232, 243, ..
Case 2: If the last digit is 0, but the digit at position 2 is not 0. Then we can subtract 1 from this digit and get a a multiple of 11. So N - 100 = 0 mod 11, or N - (99 + 1) = 0 mod 11. Examples: 320, 430, 540, ...
In the general case, at least one of the even place digits is not 0 (since the sum of the even place digits is greater than the sum of odd place digits). If it's the position 2k, then we subtract 1 from that digit, and we get N - 10^2k = 0 mod 1. But 10^2k = 100^k = (99 +1)^k = 1 mod 11.
Finally, the algorithm is to scan all the numbers N in the range [A,B] such that N = 1 mod 11. Once we find the first such N, the next one is found by adding 11. For each N, we check if (sum of even place digits) - ( sum of odd place digits) == 1. This will filter out numbers like, 309, 408, 507, etc. that don't meet the criterion.
Iterate over the array elements, and decode the type of the current element:
- if in the range of [0,127] then it's the first byte of a one byte character
- if in the range of [128,255] then it's the first byte of a two byte character. Move to the next array element, and mark it as the second byte of a two byte character.
Stop when the current pointer equals the pointer that we search for and report the type found.
Let us parse the expression into an array of lexical tokens, tokens[2*N:0] such that:
- tokens[2*i] i=0,N are the number values
- tokens[2*i-1], i=1,N are the operator values
For each pair of indices (i,j), 0 <= i <= j <= N we define:
• Exp(i,j) = the set of all the expressions can be built with the tokens from 2*i to 2*j
• Min(i,j) = the min value of all the expressions in Exp(i,j)
• Max(i,j) = the max value of all the expressions in Exp(i,j)
Max(0,N) is the max value for the entire expression.
We use dynamic programming to compute Min and Max, based on a few recursive equations.
We cache the computed values as two hash tables, hashMin, hashMax.
Complexity: O(N^3).
- ranan.fraer April 03, 2016There are O(N^2) pairs (i.j). For each pair we compute Min(i,j), Max(i,j) at most once, thanks to the caching. Iterating over k from i+1 to j, takes O(N), so the total is O(N^2 * N) = O(N^3)