kevinday.home
BAN USERI've had some time to put together a powerpoint explaining my thought process, hopefully better than my above post, you can download it here:
sites.google.com/site/kmddevelopment/Home/GoogleInterviewQuestion.ppt?attredirects=0&d=1
Sorry, I'll explain my efforts.
You have to notice a few concepts to understand my line of thinking.
1) The first item in the array can't be the first duplicate, you have to have at least a second item.
2) In c/c++(and many other languages you have 0 based indexing), this means that in a n+1 sized array you have indicies that range from 0 to n.
3) If the numbers are in the range 1 to n, you can create a modular group, ie let's say n=4, 1 mod 4 = 1, 2 mod 4 = 2, 3 mod 4 = 3, 4 mod 4 = 0, adding n to any number doesn't change where it is in the modular group, ie. 3+4=7 -> 7 mod 4 = 3
So I use the zero index item as a counter to go through the array. Adding n each time keeps the value the same in the modular group, but allows me to get an index value by then using integer division by n.
I use the other indicies as counters. Any time I see a 1 in the list I increment my 1's counter, in order to do that I add n to the value in the arr[1] position, that keeps the value at that position the same in the modular group, but also encodes that I've seen a 1.
As I iterate over the array, when I go to increment the counter if I see a value greater than n, I know I've already incremented that counter at least once. So I know I'm currently sitting at a duplicate. Since I break out of the loop at the first duplicate, I only find the first one.
Hopefully that was clear, I think I might be able to explain better with graphics. I will try to draw something up, and post a link.
Actually we know the length of the total can't exceed 101 decimal digits as 10^100 is a 1 followed by 100 zero's. However, how you go about finding d^100 in the first place is the leading question I think.
Observing:
d^100 = d^64 * d^32 * d^4
One method might be to repeatedly square the results and save off the intermediate answers along the way, requiring about 8 multiplications, but when computing d^32 and d^64 and the final 2 multiplications you'll probably benefit from a multiplication algorithm based on Fast Fourier Transforms. Most of which use a binary representation of the number. Grabbing the raw memory with a pointer and using some bit manipulation may be the way to go. Knuth discusses an algorithm linear in number of bits in TAOCP Vol 2.
I'll admit my math skills are a little rusty to explain it myself.
Another tactic might be to observe:
ln(d^100)=100 ln(d)
and mess around with that somehow.
- kevinday.home March 28, 2011
@Freddy: Good point, I can't believe I missed such a simple tweak.
- kevinday.home March 30, 2011@Anonymous: Agreed, while it's not a cure all, you could change the operation to subtraction instead of addition. Given all numbers will be in the range 1..n, and you're really only worried about changing the flags once, after a single subtraction you have numbers in the range (1-n)..0 or -n..-1 if you use the n+1 change.
Of course there's problems with that too, it can only be used on signed types, and it really doesn't fix the counter issue for iterating over the array.