# Project Euler #168: Number Rotations

# Project Euler #168: Number Rotations

trungdovan87 + 5 comments I get 100/100 point :)

Solution:

- Call it as Ab (e.g: if 2345 -> A = 234 and b = 5), and Ab have n length
We need to resolve: Ab * x = bA

=> A = {b[10^(n-1) - x]} / (10x - 1)

(I will explain later)

with:

`- x = 1 to 9 - n = 2 to m - b = 1 to 9 - length of A is equal to (n-1)`

- We can find A with above conditions. And in Java, we use BigInteger to calculate.

explain:

Ab * x = bA => (10A + b) * x = b * (10^(n-1)) + A => 10x * A + b * x = b * (10^(n-1)) + A => (10x - 1) A = b[ 10^(n-1) - x] => A = {b[10^(n-1) - x]} / (10x - 1)

akash_42414241 + 1 comment amazing!!

mini_weblab + 0 comments Agreed! :)

israellaks + 0 comments amazing!!! great job!!!

NourSamir + 1 comment it's an amazing solution, literally so creative one. How this solution inspired ?, i mean which theorem inspired you ?

trungdovan87 + 0 comments Please, remember in project Euler that "more calculation of human, less calculation of Computer"

Ryo112358 + 0 comments Could someone explain how the above algorithm to calculate A can be used as an alternative to brute force? From what I understand, we don't know the b or the x, so wouldn't we still have a ton of iterations to do regardless? Here's my current approach (brute force):

'''java

for(BigInteger i = ten; i.compareTo(upperLimit) != 1; i = i.add(one)) { rotated = rotateRight(i); if(rotated.mod(i).compareTo(zero) == 0) divisible.add(i); } System.out.println(lastFiveDigits(addElements(divisible)));

'''

**Edit:**Never mind! Not there yet but getting close...coolchand5725 + 0 comments Nailed it bro

ankits5652 + 2 comments This is not clear by last 5 digits...

shubham20_yeole + 0 comments yes. that part was confusing for me too.

wshanshan + 1 comment It was not clear.

Here is what it means (after trials and errors):

- sumVal = sum (all the numbers in the range that have the property)
- return sumVal mod 100000

shubham20_yeole + 0 comments hmm that makes sense

Marco_L_T + 4 comments #include<stdio.h> int a[105]={0,0,495,5490,55485,55480,98331,98326,98321,98316,98311,98306,41157,75329,75324,75319,75314,75309,28684,28679,28674,28669,19968,19963,62814,62809,96981,96976,90073,90068,32919,32914,32909,32904,32899,32894,86269,86264,86259,20431,20426,20421,34700,34695,50713,50708,50703,50698,93549,93544,93539,93534,27706,27701,81076,81071,74168,74163,63988,63983,6834,6829,6824,6819,6814,40986,75141,75136,75131,75126,75121,75116,28491,28486,28481,28476,28471,28466,5494,5489,5484,5479,5474,5469,12850,12845,12840,12835,28853,28848,82223,16395,16390,16385,16380,16375,59226,59221,59216,59211,59206}; int main (){ int m; scanf ("%d",&m); printf ("%d\n",a[m]); return 0; }

I made a list and successfully passed the tests. You can check the correctness of your code through the list.

rkmr039 + 0 comments [deleted]khoangcachxalam1 + 0 comments thank for your good idea (name's you : #trungdovan87 ) and your result ! i wrestle with some errors in myself code , then i run code and save result into a textbox , finally , i only println it ! with n=109 result=89574 ! n=108 result =89579 !

me_anujj + 0 comments how you had made this list ?

rishavrahul1361 + 0 comments how you creater this list

kalok87 + 2 comments What is test-case 7? Only cannot get it right, weird...

ivan_vranjic + 0 comments [deleted]ivan_vranjic + 0 comments Had the same problem. Answer must not have leading zeros. Printing answer modulo 10^5 instead of printing last 5 digits did it for me. Badly formulated desired output.

anugrahsaxena + 0 comments It says m < 100. So, for very large value of m say m=99, n will belong to values between 10 and 1e99. How are you guys dealing with the bigInteger?

For me, some easy test cases are passing but others are giving time out!

Sort 40 Discussions, By:

Please Login in order to post a comment