CODEWITHSUNDEEP
algorithmmath
user467871
user467871

Reputation:

how to find n'th digit in a number like 1491625....?

Let's concatenate the squares of numbers that start with 1. So, what is the n'th digit in this string ?

For example, the 10th digit is 4. 

1 4 9 16 25 36 49 64 81

It is just an ordinary question that come to mine ordinary mind. How can I solve this to sleep well tonight? any algorithm without looping ?

Upvotes: 8

Views: 4172

Answers (6)

aatifh
aatifh

Reputation: 2337

To solve this i have used Python Generators. My solution in Python:

def _countup(n):
    while True:
        yield n
        n += 1

def get_nth_element(n):
    i = 0 # Initialized just to keep track of iterations.
    final_string = ''
    cu_generator = _countup(0)

    while True:
        num = cu_generator.next()
        final_string += str(num * num)
        if len(final_string) > n:
            print "Number of iterations %s" % i
            return final_string[n]
        i += 1

RUN:

>>> get_nth_element(1000)
Number of iterations 229
'2'

>>> get_nth_element(10000)
Number of iterations 1637
'7'

Upvotes: 1

Ken Bloom
Ken Bloom

Reputation: 58770

This is a direct port of ephemient's Haskell answer to Scala

Iterator.from(1).flatMap(x=>(x*x).toString.iterator).drop(9).next

returns 4

O(n)

  • Iterator.from(1) creates an infinite iterator that counts 1,2,3,4,.....
  • Then (x*x).toString computes squares of each of these and turns them into strings.
  • flatMap( ... .iterator) concatenates these to become an infinite iterator of characters from the sequence in question
  • drop(9) removes the first 9 elements (indexes 0 thru 8) from the iterator and gives us a new iterator that's waiting at index 9
  • next gives us that single character.

Upvotes: 0

moinudin
moinudin

Reputation: 138347

ceil(log10(x+1)) will give you the number of digits in a number. Iterate through the squares keeping a count of the total length and once you've reached or exceeded the target length n, you know you need the mth digit of the last number for some m (easy to work out). Get the mth digit of this number by dividing by 10m-1 than taking the last digit with a mod 10.

All-in-all, constant space overhead and O(n) runtime.

Upvotes: 3

Senthil Kumaran
Senthil Kumaran

Reputation: 56833

Why would you not loop over, taking each number, squaring and incrementing the count from 1 checking at each step if you have reached n? You don't have to keep track of the whole number. It is a simple simulation exercise. I afraid, I cannot identify a pattern or formula for this.

Upvotes: 0

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272477

You can work enumerate how many 1-digit, 2-digit, 3-digit, etc. numbers there are in this sequence by taking square roots of powers-of-10. This will allow you to establish which number the n-th digit lies in. From there, it should be pretty trivial.

This should be O(log n) complexity.

Upvotes: 11

ephemient
ephemient

Reputation: 204698

Lazy infinite lists in Haskell make this trivial to express naïvely.

ghci> concat [show $ i*i | i <- [1..]] !! 9
'4'

Upvotes: 1

Related Questions