Jobs

Interviews

Discussions

Fizz Buzz

Easy

IBM

1 view

Topics:

ArraysStrings

Given an integer n, return a string array answer (1-indexed) where:

answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
answer[i] == "Fizz" if i is divisible by 3.
answer[i] == "Buzz" if i is divisible by 5.
answer[i] == i (as a string) if none of the above conditions are true.

Example 1:

Input: n = 3
Output: ["1","2","Fizz"]

Example 2:

Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]

Example 3:

Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Constraints:

1 <= n <= 10⁴

Fizz Buzz

Easy

IBM

1 view

Topics:

ArraysStrings

Given an integer n, return a string array answer (1-indexed) where:

answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
answer[i] == "Fizz" if i is divisible by 3.
answer[i] == "Buzz" if i is divisible by 5.
answer[i] == i (as a string) if none of the above conditions are true.

Example 1:

Input: n = 3
Output: ["1","2","Fizz"]

Example 2:

Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]

Example 3:

Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Constraints:

1 <= n <= 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of numbers I should consider, specifically the upper limit?
Should I handle cases where the input number is zero?
What should the output be if the number is divisible by both 3 and 5?
Is the expected output a string, and if so, what format should it follow (e.g., comma-separated, newline-separated)?
Are there any memory constraints I should be aware of, considering the potential number range?

Brute Force Solution

Approach

For the Fizz Buzz problem, we simply examine each number one at a time. We then directly check if the number meets certain criteria and print the corresponding output.

Here's how the algorithm would work step-by-step:

Start with the very first number.
Check if the number is divisible by both three and five. If it is, print 'FizzBuzz'.
If it's not divisible by both, check if the number is divisible by three. If it is, print 'Fizz'.
If it's not divisible by three, check if the number is divisible by five. If it is, print 'Buzz'.
If none of the above conditions are met, just print the number itself.
Move on to the next number and repeat the process from step two.
Continue this process until you have checked all the numbers up to the last number in the required range.

Code Implementation

def fizz_buzz(number_limit):
    for number_index in range(1, number_limit + 1):
        # Check divisibility by both 3 and 5 first
        if number_index % 3 == 0 and number_index % 5 == 0:
            print('FizzBuzz')

        # Check divisibility by 3
        elif number_index % 3 == 0:
            print('Fizz')

        # Check divisibility by 5
        elif number_index % 5 == 0:
            print('Buzz')

        # If none of the conditions are met, print the number
        else:
            print(number_index)

# Example usage:
fizz_buzz(15)

Big(O) Analysis

Time Complexity

O(n) – The given Fizz Buzz solution iterates through each number from 1 to n. For each number, it performs a constant number of checks (divisibility by 3 and 5) and prints the corresponding output. Since the number of operations scales linearly with the input size n, the time complexity is O(n).

Space Complexity

O(1) – The algorithm described processes numbers one at a time and prints output based on divisibility. It does not store any numbers or intermediate results in data structures like arrays or hash maps. Therefore, the space required remains constant regardless of the input range size, N, as only a few variables for iteration and divisibility checks are used.

Optimal Solution

Approach

The Fizz Buzz problem can be solved efficiently by checking divisibility and building the output string piece by piece. We focus on creating each output element directly instead of needing to test every possible value. This avoids unnecessary calculations and creates a clean solution.

Here's how the algorithm would work step-by-step:

For each number, first check if it's divisible by both 3 and 5. If it is, the result for this number is 'FizzBuzz'.
If the number isn't divisible by both, check if it's divisible by 3. If it is, the result for this number is 'Fizz'.
If the number isn't divisible by 3, check if it's divisible by 5. If it is, the result for this number is 'Buzz'.
If the number isn't divisible by 3 or 5, the result for this number is just the number itself.
Repeat these steps for each number in the given range to create the final output.

Code Implementation

def fizzBuzz(number):
    result_list = []
    for current_number in range(1, number + 1):
        output_string = ""
        # Check divisibility by 3 and 5 first for 'FizzBuzz'
        if current_number % 3 == 0 and current_number % 5 == 0:
            output_string = "FizzBuzz"

        # Check divisibility by 3 for 'Fizz'
        elif current_number % 3 == 0:
            output_string = "Fizz"

        # Check divisibility by 5 for 'Buzz'
        elif current_number % 5 == 0:
            output_string = "Buzz"

        # If not divisible by 3 or 5, keep the number.
        else:
            output_string = str(current_number)

        result_list.append(output_string)
    return result_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each number from 1 to n. For each number, it performs a fixed number of checks (divisibility by 3 and 5). The number of operations within the loop is constant, regardless of the input size n. Thus, the time complexity is directly proportional to n, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm generates a result for each number in the given range. Since the plain English description directs us to create an output for each number from 1 to N (where N is the upper bound of the range), we essentially build a list or array containing N strings ('Fizz', 'Buzz', 'FizzBuzz', or the number itself). Therefore, the auxiliary space required grows linearly with the input size N. The space complexity is O(N).

Edge Cases

Case	How to Handle
Input n is zero or negative	Return an empty list or raise an IllegalArgumentException, as the problem typically defines a positive range.
Input n is extremely large, approaching integer limits	The solution should use appropriate data types (e.g., long if necessary) and consider potential performance impacts of generating a large list.
n is 1	The solution should return a list containing only '1'.
n is divisible by both 3 and 5	Ensure 'FizzBuzz' is printed for numbers divisible by both 3 and 5.
Language specific integer overflow	Handle potential integer overflows if the problem is extended (e.g., calculating the sum of numbers) by using larger data types or modular arithmetic.
Input is not an integer	Handle the case where the input is not an integer by either raising a TypeError or casting to an integer (if appropriate based on problem requirements).
Memory constraints for large n	If n is extremely large, consider a generator or iterator approach to avoid loading the entire list into memory at once.
Edge case where 3 and 5 are factors of very large number and memory is limited	For very large n, yield results incrementally as needed to manage memory consumption, only storing the current result in memory.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of numbers I should consider, specifically the upper limit?
Should I handle cases where the input number is zero?
What should the output be if the number is divisible by both 3 and 5?
Is the expected output a string, and if so, what format should it follow (e.g., comma-separated, newline-separated)?
Are there any memory constraints I should be aware of, considering the potential number range?

Brute Force Solution

Approach

For the Fizz Buzz problem, we simply examine each number one at a time. We then directly check if the number meets certain criteria and print the corresponding output.

Here's how the algorithm would work step-by-step:

Start with the very first number.
Check if the number is divisible by both three and five. If it is, print 'FizzBuzz'.
If it's not divisible by both, check if the number is divisible by three. If it is, print 'Fizz'.
If it's not divisible by three, check if the number is divisible by five. If it is, print 'Buzz'.
If none of the above conditions are met, just print the number itself.
Move on to the next number and repeat the process from step two.
Continue this process until you have checked all the numbers up to the last number in the required range.

Code Implementation

def fizz_buzz(number_limit):
    for number_index in range(1, number_limit + 1):
        # Check divisibility by both 3 and 5 first
        if number_index % 3 == 0 and number_index % 5 == 0:
            print('FizzBuzz')

        # Check divisibility by 3
        elif number_index % 3 == 0:
            print('Fizz')

        # Check divisibility by 5
        elif number_index % 5 == 0:
            print('Buzz')

        # If none of the conditions are met, print the number
        else:
            print(number_index)

# Example usage:
fizz_buzz(15)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

For each number, first check if it's divisible by both 3 and 5. If it is, the result for this number is 'FizzBuzz'.
If the number isn't divisible by both, check if it's divisible by 3. If it is, the result for this number is 'Fizz'.
If the number isn't divisible by 3, check if it's divisible by 5. If it is, the result for this number is 'Buzz'.
If the number isn't divisible by 3 or 5, the result for this number is just the number itself.
Repeat these steps for each number in the given range to create the final output.

Code Implementation

def fizzBuzz(number):
    result_list = []
    for current_number in range(1, number + 1):
        output_string = ""
        # Check divisibility by 3 and 5 first for 'FizzBuzz'
        if current_number % 3 == 0 and current_number % 5 == 0:
            output_string = "FizzBuzz"

        # Check divisibility by 3 for 'Fizz'
        elif current_number % 3 == 0:
            output_string = "Fizz"

        # Check divisibility by 5 for 'Buzz'
        elif current_number % 5 == 0:
            output_string = "Buzz"

        # If not divisible by 3 or 5, keep the number.
        else:
            output_string = str(current_number)

        result_list.append(output_string)
    return result_list

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is zero or negative	Return an empty list or raise an IllegalArgumentException, as the problem typically defines a positive range.
Input n is extremely large, approaching integer limits	The solution should use appropriate data types (e.g., long if necessary) and consider potential performance impacts of generating a large list.
n is 1	The solution should return a list containing only '1'.
n is divisible by both 3 and 5	Ensure 'FizzBuzz' is printed for numbers divisible by both 3 and 5.
Language specific integer overflow	Handle potential integer overflows if the problem is extended (e.g., calculating the sum of numbers) by using larger data types or modular arithmetic.
Input is not an integer	Handle the case where the input is not an integer by either raising a TypeError or casting to an integer (if appropriate based on problem requirements).
Memory constraints for large n	If n is extremely large, consider a generator or iterator approach to avoid loading the entire list into memory at once.
Edge case where 3 and 5 are factors of very large number and memory is limited	For very large n, yield results incrementally as needed to manage memory consumption, only storing the current result in memory.