This is one of those problems where the clean idea matters more than the amount of code. For 1195. Fizz Buzz Multithreaded, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are fizz, buzz, fizzbuzz, number.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The code keeps the moving pieces local, so the main idea stays visible.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 1428 ms, faster than 12.41% of C++ online submissions for Fizz Buzz Multithreaded.
02//Memory Usage: 9.2 MB, less than 100.00% of C++ online submissions for Fizz Buzz Multithreaded.
03
04class FizzBuzz {
05private:
06 int n;
07 int cur;
08 mutex mtx;
09
10public:
11 FizzBuzz(int n) {
12 this->n = n;
13 this->cur = 1;
14 }
15
16 // printFizz() outputs "fizz".
17 void fizz(function<void()> printFizz) {
18 while(this->cur <= this->n){
19 if(this->cur % 15 != 0 && this->cur % 3 == 0){
20 mtx.lock();
21 printFizz();
22 this->cur++;
23 mtx.unlock();
24 }
25 }
26 }
27
28 // printBuzz() outputs "buzz".
29 void buzz(function<void()> printBuzz) {
30 while(this->cur <= this->n){
31 if(this->cur % 15 != 0 && this->cur % 5 == 0){
32 mtx.lock();
33 printBuzz();
34 this->cur++;
35 mtx.unlock();
36 }
37 }
38 }
39
40 // printFizzBuzz() outputs "fizzbuzz".
41 void fizzbuzz(function<void()> printFizzBuzz) {
42 while(this->cur <= this->n){
43 if(this->cur % 15 == 0){
44 mtx.lock();
45 printFizzBuzz();
46 this->cur++;
47 mtx.unlock();
48 }
49 }
50 }
51
52 // printNumber(x) outputs "x", where x is an integer.
53 void number(function<void(int)> printNumber) {
54 while(this->cur <= this->n){
55 if(this->cur % 3 != 0 && this->cur % 5 != 0){
56 mtx.lock();
57 printNumber(this->cur);
58 this->cur++;
59 mtx.unlock();
60 }
61 }
62 }
63};
64
65//using condition_variable and mutex
66//https://leetcode.com/problems/fizz-buzz-multithreaded/discuss/387994/C%2B%2B-mutex-condition_variable-please-suggest-improvements
67//Runtime: 48 ms, faster than 57.33% of C++ online submissions for Fizz Buzz Multithreaded.
68//Memory Usage: 9.1 MB, less than 100.00% of C++ online submissions for Fizz Buzz Multithreaded.
69class FizzBuzz {
70private:
71 int n;
72 int count;
73 mutex m;
74 condition_variable cv;
75
76public:
77 FizzBuzz(int n) {
78 this->n = n;
79 this->count = 1;
80 }
81
82 // printFizz() outputs "fizz".
83 void fizz(function<void()> printFizz) {
84 while(true){
85 unique_lock<mutex> lock(m);
86 //wait for lock
87 while(count <= n && !(count % 3 == 0 && count % 5 != 0)){
88 cv.wait(lock);
89 }
90 //lock acquired
91 if(count > n) break;
92 printFizz();
93 ++count;
94 //release lock
95 cv.notify_all();
96 }
97 }
98
99 // printBuzz() outputs "buzz".
100 void buzz(function<void()> printBuzz) {
101 while(true){
102 unique_lock<mutex> lock(m);
103 while(count <= n && !(count % 3 != 0 && count % 5 == 0)){
104 cv.wait(lock);
105 }
106 if(count > n) break;
107 printBuzz();
108 ++count;
109 cv.notify_all();
110 }
111 }
112
113 // printFizzBuzz() outputs "fizzbuzz".
114 void fizzbuzz(function<void()> printFizzBuzz) {
115 while(true){
116 unique_lock<mutex> lock(m);
117 while(count <= n && !(count % 15 == 0)){
118 cv.wait(lock);
119 }
120 if(count > n) break;
121 printFizzBuzz();
122 ++count;
123 cv.notify_all();
124 }
125 }
126
127 // printNumber(x) outputs "x", where x is an integer.
128 void number(function<void(int)> printNumber) {
129 while(true){
130 unique_lock<mutex> lock(m);
131 while(count <= n && (count % 3 == 0 || count % 5 == 0)){
132 cv.wait(lock);
133 }
134 if(count > n) break;
135 printNumber(count);
136 count++;
137 cv.notify_all();
138 }
139 }
140};
141
142/*
143The error of unique_lock<mutex> lock;(it should be unique_lock<mutex> lock(m);):
144AddressSanitizer:DEADLYSIGNAL
145=================================================================
146==29==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000010 (pc 0x7f95fb0ff193 bp 0x7f95ea79cd40 sp 0x7f95ea79cbd8 T4)
147==29==The signal is caused by a READ memory access.
148==29==Hint: address points to the zero page.
149 #0 0x7f95fb0ff192 in __pthread_mutex_unlock_usercnt (/lib/x86_64-linux-gnu/libpthread.so.0+0xb192)
150 #1 0x7f95fb1010d6 in __pthread_cond_wait (/lib/x86_64-linux-gnu/libpthread.so.0+0xd0d6)
151 #2 0x7f95fcdac3ab in std::condition_variable::wait(std::unique_lock<std::mutex>&) (/usr/local/lib64/libstdc++.so.6+0xb53ab)
152 #5 0x7f95fcdb1a6e (/usr/local/lib64/libstdc++.so.6+0xbaa6e)
153 #6 0x7f95fb0fb493 in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x7493)
154 #7 0x7f95fb805ace in __clone (/lib/x86_64-linux-gnu/libc.so.6+0xe8ace)
155AddressSanitizer can not provide additional info.
156SUMMARY: AddressSanitizer: SEGV (/lib/x86_64-linux-gnu/libpthread.so.0+0xb192) in __pthread_mutex_unlock_usercnt
157Thread T4 created by T0 here:
158 #0 0x7f95fd0c22d0 in pthread_create (/usr/local/lib64/libasan.so.5+0x492d0)
159 #1 0x7f95fcdb1cf4 in std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) (/usr/local/lib64/libstdc++.so.6+0xbacf4)
160 #2 0x7f95fb73d2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
161==29==ABORTING
162*/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.