Just split the input list as a prefix of a few, and then a repeat. The goal of the shortest total distance between them is constant. You just need to measure the number of ints between each of the 8 repeating distances.
So the runtime of the solution is bounded by a constant for arbitrarily large input? There must be some great cleverness at play to produce an output with size linear in the input size without taking time proportional to the size of the output.
For those who aren't getting anonymoushn's point - outputting a O(n) bytes will take O(n) time, no matter if your processing per piece of output is fast or slow. In fact, this optimization will only give constant-time speedup from an iterative or functional solution - those do some (very cheap) numerical operations for every number in the range, while this does (even cheaper) array lookup for 7 out of every 15 numbers. A decent-sized constant-factor speedup is still only a constant-factor speedup.
That assumes you're providing the output as a list of elements. Since it's a contiguous sequence, you can uniquely identify a particular output as a tuple (start, length). So you can get a constant-time solution if you're allowed to assume the input is valid (and have a constant-time way of getting the length of the input, I guess).
On the other hand, checking to ensure that the input represents a valid sequence is going to be O(n) in the size of the input no matter what you do...
It's just modular math. The output is fizz if the output is orthogonal to 0 mod 3, and buzz if it is orthogonal to 0 mod 5. It's fizzbuzz when it's 0 mod 15.
Now, since 15 is divisible by 3, it's easy to see that x = 0 mod 3 iff x = {0, 3, 6, 12} mod 15, and similarly x = 0 mod 5 iff x = {0, 5, 10} mod 15. So you can see now that you can determine the output for a given index based on the remainder after dividing by 15, so the sequence must repeat every 15 elements.
Matching the the sequence of fizz/buzz/fizbuzz disregarding numbers is a repetitive case.
Start with
Just split the input list as a prefix of a few, and then a repeat. The goal of the shortest total distance between them is constant. You just need to measure the number of ints between each of the 8 repeating distances.For example:
So you would match against the list [Fizz, Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz].