Sam and substrings Discussions | Algorithms | HackerRank
  • + 16 comments

    Consider an example with string "6789" to understand the logic. The sub-strings of "6789" are 6, 7, 8, 9, 67, 78, 89, 678, 789, 6789.

    Now, sub-string "789" can be expressed as 700 + 80 + 9. If all the substrings are expressed in similar way, we just need to know position and frequency of each digit in all the substrings combined, to get the total sum.

    For substring "6789", we have :

            Frequency in substrings at positions
    Digit   Unit    Ten     Hundred     Thousand        Sum
    6       1       1       1           1           = 6*1*1111
    7       2       2       2                       = 7*2*111
    8       3       3                               = 8*3*11
    9       4                                       = 9*4*1
    

    This example gives the insight that for a string of length n, contribution by a digit x at position k will be : x* k* 11..1(n-k+1 times '1').


    Translating the same for the above code. Loop runs through all the digits :

    f takes values 1, 11, 111, 1111 ... (and so on)

    s[i]-'0' is the digit x as discussed in above example.

    i+1 is the position k.