Tuesday, April 3, 2012

An Improvement on Counting Subsequences in Pi

So I was thinking about this problem some more this evening while watching Dora the Explorer with my daughter, and I realized that I could use the same technique I was using to add up occurrences of the subsequence to track occurrences of the earlier portion of the subsequence and I would require only 3 counters and it would run in linear time. This solution should also work for subsequences of other lengths and remain O(n) bound.

Here is the solution:

1. While ! EOF, scan a digit
2. If it is the first digit in the subsequence, increment a counter.
3. If it is the second digit in the subsequence, increment second counter by current value of counter tracked in 2
4. If it is the third digit in the subsequence, increment occurrences counter by the current value of the counter tracked in 3.
5. goto 1


Here is the output from the old version:

sequence 1, 2, 3: 1000000 167568126814676 10031551523

real 0m41.618s
user 0m41.436s
sys 0m0.004s

Here is the output from the new version:

sequence 1, 2, 3: 1000000 167568126814676 1300014

real 0m0.019s
user 0m0.018s
sys 0m0.001s


As stated in the previous post on this, the first number is the number of digits scanned, the 2nd is the number of occurrences of the subsequence, and the 3rd is the number of logical operations.

No comments:

Post a Comment