number of different numbers in a given binary string and their sum
I'am thinking of this problem and don't have an idea where to start with >>
We are given a binary string and is there any possible way other than brute force to find number of different numbers(their binary representations as sub-strings in the given string) it consists of and their sum.
if given binary is: "1101" then the possible numbers it consists are -
0, 1, 2, 3, 5, 6, 13
sum = 0 + 1 + 2 + 3 + 5 + 6 + 13 = 30
Have a look at Suffix Trees, they let you find the count of different substrings in a string in O(n).
To find the sum of the different numbers I would recommend you actually compute the suffix tree for the reversed string, in other words you are computing a prefix tree.
You can then compute for each prefix node the sum of all distinct numbers underneath it.
The reason a reversed string is better is that we adding a digit to the end of a number is easy (multiply by 2 and add the digit), and so we can do this operation to our subtotals.
If we try to do the same with a suffix tree, we would want to add a digit to the front of all our numbers, but the numbers are of different lengths so it is hard to see what operation you can do to the total.
Take care when counting the prefix trees to ignore branches that start with 0 or you will also count 001 and 01 and 1 as being distinct.
I believe this should result in an O(n) cost for the entire operation where n is the number of digits in your string.