TheRandomGuy
BAN USER@Tarun, I dont thint the above solution is correct, as I said earlier - the question does not clarify anything about the "array", and to implement counting sort, we must know the range of the integers.
The anonymous post right at the start of this page clarifies further assumptions. I like that answer.
If the bounds on the input numbers are known then the answer is O(n), due to counting sort, I am not sure of what to do when we don't know how to do it.
- TheRandomGuy March 13, 2010Say you have to multiply 'a' by 'b'.
Find a smallest number 'c' which is greater than 'b' and is a power of 2 (you would be interested in this because you would want to shift bits - efficient method.) so if c = 2^k then a.c = (a << k) right shifting 'a' by k bits.
Now, we know that a.c is greater than a.b, so we would want to subtract the difference [(c-b).n] off the *product*,
simply put: b = ( c - delta ) -> a.b = (c-delta) . a -> a.b = a.c - a.delta
[delta is known in all cases since you pick 'c' and 'b' is already given]
No, Trie is a data structure, typically used to store dictionary type DSs [...../wiki/Trie]
- TheRandomGuy March 13, 2010
I would've clarified - do you mean "checked" and "unchecked" exceptions?
- TheRandomGuy March 13, 2010