abc1.picasa
BAN USERChallange here was to determine the state of running stream of bits, not mathematical problem of 'divisibility by 3'. If you can solve using % operator and without using extra space, its fine. And if you see the scalabilty of solution,you'll find, this is the best solution.
- abc1.picasa December 09, 2011True, you nailed it, great job. while going through other solutions i felt that yours is a generalization of majority voting algorithm (correct me if thats wrong).
However, on a curious note, you could have used 2 arrays, for std::map, and would have avoid that logM factor. (i know thats constant anyway). Thanks for posting great solution.
Solution of 'difference between sum of odd and even bits divisble by 3' is correct
However its not scalable. So if i change problem to find out if its divisible by 7, we need to rework. So we should think about scale machine kind of solution.
Here is my understanding.
lets always store the remainder. and when new bits arrive shift remainder left and put new bit at lsb. if this is divisible by 3, signal it out, divide this number by 3, keep the remainder, wait for next bit.
Now i just notice, code for this is posted by srikant aggarwal (thanks to you sir.)
that code will work for any number 3 or 2300 (as long as an 'int' can hold it).
Lets assume all the gas stations are node on a circular linked list.
- abc1.picasa January 30, 2012Foreach node assign a value = fuel (in km) - distance to next station (in km)
Now this becomes a circular array.
Our problem is transformed into the problem where we need to find a subarray with maximum sum. (Standard problem, and it can be solved in o(n) .. search maximum subarray in wikipedia, in case you are not aware of it).
Correct me if any of my above assuptions are incorrect.