Hiring Questions, Problem 1

A colleague of mine once posted a hiring question to ask prospective developers: “What is the least significant 10 digits of the series: 1^{1}+2^{2}+3^{3} .. 1000^{1000} ?”

The trick of course is to recognize that it’s solved with modular exponentiation. He presented a page of java code which was akin to what he was looking for. I did a one-liner on the bash command line and flunked the test. (He was looking for java programmers.)

    \[\LARGE\Bigg(\sum_{n=1}^{1000} n^{n} \bmod 10^{10}\Bigg) \bmod 10^{10}\]

My one liner:

$ for i in {1..1000} ; do echo "$i $i 10000000000|p" | dc ;  done | awk '{t=($1+t)%1e10} END {print t}'
9110846700

I like my recursive awk solution better however, as it was more fun..

$ echo 1000 | awk '
> function powermod(n,p) {
>   if (p == 1)  return n
>   else return  n*powermod(n,p-1) % 1e10
> }
> function add(n) {
>   if (n == 1)  return 1
>   return (add(n-1) + powermod(n,n)) % 1e10
> }
> 
> NF { print add($1) % 1e10 }
> '
9110846700

 
How would you solve it in your favourite language?

Leave a Reply

Your email address will not be published. Required fields are marked *