very smart! You duplicate the number while only keeping last few digits, to get basically O(n) complexity. Much better than my idea.