Leetcode – Fizz Buzz Solution in Python

Spread the love

Introduction

In this extensive article, we will be focusing on one of the classic programming problems: the ‘Fizz Buzz’ problem. It is categorized as an easy problem on Leetcode, but it is essential as it is frequently used in coding interviews to assess basic programming skills. We will discuss different approaches to solve the problem in Python, analyze their time complexities, and understand the underlying concepts.

Problem Statement

The ‘Fizz Buzz’ problem is listed as problem number 412 on Leetcode. The problem statement is as follows:

Write a program that outputs the string representation of numbers from 1 to n. But for multiples of three, it should output “Fizz” instead of the number, and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five, output “FizzBuzz”.

Example:

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

Approach 1: Naive Solution

  1. Create an empty list to store the results.
  2. Iterate from 1 to n.
  3. For each number, check if it is divisible by both 3 and 5, if so, append “FizzBuzz” to the result list.
  4. If not, check if it is divisible by 3, and append “Fizz” if it is.
  5. If not, check if it is divisible by 5, and append “Buzz” if it is.
  6. Otherwise, append the string representation of the number to the list.
  7. Return the list.
def fizzBuzz(n):
    result = []

    for i in range(1, n + 1):
        if i % 3 == 0 and i % 5 == 0:
            result.append("FizzBuzz")
        elif i % 3 == 0:
            result.append("Fizz")
        elif i % 5 == 0:
            result.append("Buzz")
        else:
            result.append(str(i))

    return result

Time Complexity

The time complexity of this approach is O(n) since there is a single loop that iterates through numbers from 1 to n.

Approach 2: Using String Concatenation

  1. Create an empty list to store the results.
  2. Iterate from 1 to n.
  3. For each number, create an empty string.
  4. If the number is divisible by 3, add “Fizz” to the string.
  5. If the number is divisible by 5, add “Buzz” to the string.
  6. If the string is empty, it means the number is not divisible by 3 or 5, so convert the number to a string.
  7. Append the string to the result list.
  8. Return the list.
def fizzBuzz(n):
    result = []

    for i in range(1, n + 1):
        entry = ''
        if i % 3 == 0:
            entry += "Fizz"
        if i % 5 == 0:
            entry += "Buzz"
        if not entry:
            entry = str(i)
        
        result.append(entry)

    return result

Time Complexity

The time complexity for this approach is also O(n) since we are iterating through numbers from 1 to n. However, the number of condition checks is reduced compared to the naive solution.

Approach 3: Using a Dictionary for Modulo Operations

  1. Create an empty list to store the results.
  2. Create a dictionary with keys as 3 and 5 and values as “Fizz” and “Buzz”.
  3. Iterate from 1 to n.
  4. For each number, create an empty string.
  5. Iterate through the keys in the dictionary, for each key if the number is divisible by the key, concatenate the corresponding value to the string.
  6. If the string remains empty, append the string representation of the number to the list; otherwise, append the string.
  7. Return the list.
def fizzBuzz(n):
    result = []
    fizz_buzz_dict = {3: "Fizz", 5: "Buzz"}

    for i in range(1, n + 1):
        entry = ''
        for key in fizz_buzz_dict.keys():
            if i % key == 0:
                entry += fizz_buzz_dict[key]
        if not entry:
            entry = str(i)
        
        result.append(entry)

    return result

Time Complexity

This approach also has a time complexity of O(n). The nested loop does not affect the time complexity significantly as the dictionary has a constant number of entries.

Conclusion

The ‘Fizz Buzz’ problem is a classic programming problem that is often used to evaluate basic programming skills. It involves iterating through numbers and applying simple conditions. The problem can be solved using various approaches with a linear time complexity. Understanding different methods for solving this problem is essential, especially for beginners, as it not only helps in grasping basic programming concepts but also in efficiently using data structures like dictionaries.

Leave a Reply