The Unlucky 13 Challenge in HackerEarth

Question

I recently came across this coding challenge - The Unlucky number 13. (The last problem in the section)

Problem Statement:

Write a program to calculate the total number of strings that are made of exactly N characters. None of the strings can have "13" as a substring. The strings may contain any integer from 0-9, repeated any number of times.

Input: N is taken as input where 0<= N <= 1000000009.

Output: The output should be the answer modulo 1000000009.

My Solution:

I tried to solve it using a simple equation I came up with.

ans = 10^n - ((10^(n-2)) * (n-1))

Subtracting the possibilities with 13 as substring from the total number of possibilities.

I wrote the code in Swift. It works when N is small. But I get a runtime error on submission (probably when N is large).

Here is my code:

let input = Int(readLine()!)
if let n = input as? Int{
    var ans = getPowerOfTen(n)
    ans = ans - getPowerOfTen(n-2) * (n - 1)
    print(ans % 1000000009)
}

// Did not import any library to calculate the power   

 func getPowerOfTen(_ num: Int)->Int{
        var ans = 1
        var n = num
        while(n > 0){
            ans = ans * 10
            n = n - 1
        }
        return ans
 }

I was hoping to get help for two questions.

1. Could you help me find the run time issue?

   This is the screenshot of the runtime error I get from the site.

2. Could there be a better way to solve this?

I found this in Array & Strings problem section. I did not use any array though. I think this equation works.

Answer 1

The formula seems correct. There are two problems with your solution.

1: Time complexity
2: Overflow Issue

---

Time complexity

You are using naïve technique when calculating 10^n mod m. You are using a simple loop from 1 to n which results in a complexity of O(n). There is a very popular technique known as Binary Exponentiation of calculating a^b mod m in O(logn). This technique is used widely in competitive programming to solve various questions.

---

Overflow Issue

Inside the while loop, you are repeatedly updating ans like this:

ans = ans * 10

When the value becomes big enough, ans will become negative since it will unable to store that value. This is known as Overflow. One good way to spot that there is a chance that overflow may happen, is when in the question it is mentioned:

The output should be the answer modulo 1000000009

This is a sign that the program setter themselves know that the calculation will be big so they ask to output the answer in this format.

---

I have not provided the algorithm for Binary Exponentiation as it already there in the provided link. The algorithm used there also takes care of overflow issue. I have also provided another link for Integer Overflow in case you want to check it out.

If you still face any trouble, do comment.