Pavel Kalinnikov
BAN USERToo slow.
- Pavel Kalinnikov November 19, 2015Notice that in step IV you don't have to sort those digits. Since they are descending (by construction), you can just reverse those. And you get a linear algorithm.
- Pavel Kalinnikov January 12, 2015Interesting thing is that this incorrect solution is voted up, while the correct O(length) algorithm I proposed is voted down. People don't even understand how to judge solutions.
- Pavel Kalinnikov November 16, 2014The initial post doesn't state this idea. It says nothing about what would happen if we don't find anything for the last digit.
You're right, akash.gpta, but... This solution can take O(L^2) time where L is a lenght of the number. Check your algo on the following number: 8988...8877..7766..6655..5544..4433..3322..2211..1100..00
We can do better - in O(L) time.
This solution seems work in O(L^2) worst case where L is a length of a number. For example consider the number: 8988...8877..7766..6655..5544..4433..3322..2211..1100..00
For every digit except 9 you will go till the beginning of the number trying to find something less than this digit, and fail. And only digit 9 will succeed.
This is not quite right. For example your solution would fail on this input: 5981. The proper answer is 8159. But "Take the last digit. Find the first digit on the left that's smaller" will find nothing because there is no digit on the left that's smaller than the last (1 is the smallest digit here).
- Pavel Kalinnikov November 13, 2014This is a "next permutation" problem and the algorithm for solving it is as follows:
0. Let us assume that digits are numbered 0..(L-1) starting from the lowest digits.
1. Find the first (starting from the lowest) digit d[i] such as:
d[i] < d[i-1], 0 < i < L
2. Find the first (starting from the lowest) digit d[j], which is greater than d[i]:
d[j] > d[i], 0 <= j < i
3. Swap(d[i], d[j])
4. Reverse digits from 0 to (i-1)
The complexity of this algo is O(L)
Also this solution can be easily generalized to solve the whole family of problems "N numbers appear exactly K times, and 1 number appears M times (M != K)", and the complexity will be O(N log K) with O(log K) additional memory.
- Pavel Kalinnikov November 12, 2014Hey guys, check it out. The idea is to make a bitwise sum of all the numbers modulo 3 (I mean, every i-th bit of the result is a sum modulo 3 of i-th bit across all the numbers). Since we have no such an operation, let's emulate it using bitwise operations. Let us have 2 words, representing our sum modulo 3 (one word is for lower bit of the sums, and one word for higher bit). All we need to do is to implement an operation (x + y) mod 3, where x is a 2-bit number, and y is a 1-bit number. And we want to do it in O(1) using bitwise operaions. If you know how computer adders/counters work, it is pretty much it (check Half_adder and Counter on wikipedia).
Here is the code of a function:
template<typename T>
T getUniqueNumber(const T *begin, const T *end) {
T low = 0, high = 0;
for (; begin + 1 <= end; ++begin) {
high ^= low & *begin;
low ^= *begin;
const T overflow = high & low;
low ^= overflow;
high ^= overflow;
}
return low;
}
This task can be solved in O(N + M) time.
- Pavel Kalinnikov November 19, 2015First, it is obvious, that a greedy algorithm should be used, i.e. the first digit should be as big as possible and as left as possible in respective array.
Let us divide both arrays into 10 buckets, where a bucket number i (0 <= i <= 9) should contain a list of all i's positions in the respective array.
Algorithms performs K steps, each finds a max. possible digit for the current position. We should maintain 2 indices - one for the rightmost digit taken from the first array, and one for the second array. Initially these indices are both zero (or -1 depending on implementation). On each of K steps go through 10 buckets of both arrays in decreasing order of digit and try to find a position such that (number of remaining elements in the respective array after this index) + (number of remaining elements in the other array) is at least K-T, where T is a number of performed steps. When iterating through buckets, if we meet a position that is to the left of current rightmost index for the respective array, we can drop this position and never consider it again. Otherwise, if it is to the right of the rightmost position, we immediately discard it, put to the resulting array, and go to the next step immediately.
It is easy to see, that each element will be considered only once: it will either be dropped, or put into result. Thus, the complexity has an order of total number of elements = O(N + M).