5 ms·
TLDR: Here's a constant-time solution: http://codepad.org/Id9eu0Ax http://codepad.org/Id9eu0Ax Matching the the sequence of fizz/buzz/fizbuzz disregarding num
by harpastum 14y ago
TLDR: Here's a constant-time solution: http://codepad.org/Id9eu0Ax http://codepad.org/Id9eu0Ax
Matching the the sequence of fizz/buzz/fizbuzz disregarding numbers is a repetitive case.
Start with
3 Fizz
5 Buzz
6 Fizz
9 Fizz
10 Buzz
12 Fizz
15 FizzBuzz
18 Fizz
20 Buzz
21 Fizz
24 Fizz
25 Buzz
27 Fizz
30 FizzBuzz
[repeats]
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:
3 -> Fizz
+2 -> Buzz
+1 -> Fizz
+3 -> Fizz
+1 -> Buzz
+2 -> Fizz
+3 -> FizzBuzz
+3 -> Fizz
+2 -> Buzz
+1 -> Fizz
+3 -> Fizz
+1 -> Buzz
+2 -> Fizz
+3 -> FizzBuzz
So you would match against the list [Fizz, Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz].
- deleted 14y ago[deleted]
- anonymoushn 14y agoSo 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.
- bdonlan 14y agoIt'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.
- dspeyer 14y ago> Shipper: Hmmm. I don't think that list is valid... > Google: Good. So your program will have to detect that. Your program might receive bad input, and it's your responsibility to output an error code if so.
- azernik 14y agoFor 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.
- jbri 14y agoThat 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...
- deleted 14y ago[deleted]