We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I realized following,
1. As k <= 50, only last two digits of n matter, so just calculate (n ^ n)%100, which can be simplified as ((n%100) ^ (n%100)) % 100.
2. But you don't need to do this for all n, as there are only 100 possible values for n % 100.
3. This gives us ~53 numbers which can appear as the last two digits of n^n, and we can easily count how many numbers are there for each such number. The same last digits repeat every 100 numbers.
4. The remaining issue is how many ways can be combine these numbers to get a certain remainder. For example, if K = 3, we count do take any 3 numbers from those numbers who's square ends with 1. But I am not able to extend this to calculate all such combos.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #250: 250250
You are viewing a single comment's thread. Return to all comments →
[Spoiler]
I realized following, 1. As k <= 50, only last two digits of n matter, so just calculate (n ^ n)%100, which can be simplified as ((n%100) ^ (n%100)) % 100. 2. But you don't need to do this for all n, as there are only 100 possible values for n % 100. 3. This gives us ~53 numbers which can appear as the last two digits of n^n, and we can easily count how many numbers are there for each such number. The same last digits repeat every 100 numbers. 4. The remaining issue is how many ways can be combine these numbers to get a certain remainder. For example, if K = 3, we count do take any 3 numbers from those numbers who's square ends with 1. But I am not able to extend this to calculate all such combos.