CODEWITHSUNDEEP
algorithm
jatt
jatt

Reputation: 11

How to find Nth Armstrong number in less than O(n) time complexity?

Series of armstrong numbers is as 1,2,3,4,5,6,7,8,9,153...... How we can find Nth armstrong number in less than O(n) time complexity if possible.

I have tried the solution by traversing from 1 to max_int and checking whether the iTH number is armstrong or not.If yes, count it and add to a list. Then return list[n-1] for the nth armstrong number.

Upvotes: 1

Views: 368

Answers (2)

suketup
suketup

Reputation: 469

This may not be optimal solution, but As per this article,

a total of 88 narcissistic(armstrong) numbers exist in base 10, as proved by D. Winter in 1985 and verified by D. Hoey.

So, possibly you can add those numbers in a list and use it to return nth Armstrong Number. This way returning nth number would only take O(1) time.

It could avoid going through all the numbers and check whether it is Armstrong Number or not.

Also, based on programming language you are using, you may not need all 88 numbers, as some numbers are too long(39 digits) and may not be supported by many languages.

Upvotes: 2

Luka Rahne
Luka Rahne

Reputation: 10457

There is no need to check for all permutations. If you try [1,2,3,4] than you check if resulting number when digits of result is sorted equals 1234. Any other permutations is not required to check for example [3,2,1,4]. This reduce complexity for factor n! where n is number of digits. For example cheeking all 9 digits numbers this way requires approx 28e3 checks instead 1e9.

Upvotes: 0

Related Questions