Sam and substrings Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sam and substrings
You are viewing a single comment's thread. Return to all 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 :
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.