easy Fizz Buzz

Problem Statement

Given an integer n, return a 1-indexed string array res where:

• res[i] == "FizzBuzz" if i is divisible by 3 and 5.
• res[i] == "Fizz" if i is divisible by 3.
• res[i] == "Buzz" if i is divisible by 5.
• res[i] == i (as a string) if above all conditions are false.

Examples

• Example 1:

  • Input: 4
  • Expected Output: ["1", "2", "Fizz", "4"]
  • Justification: 3 is divisible by 3, so it's replaced with "Fizz". The rest are not divisible by 3 or 5, so they remain unchanged.

• Example 2:

  • Input: 7
  • Expected Output: ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7"]
  • Justification: 3 and 6 are divisible by 3 (replaced with "Fizz"), 5 is divisible by 5 (replaced with "Buzz"), and the rest are printed as is.

• Example 3:

  • Input: 16
  • Expected Output: ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz", "16"]
  • Justification: 3, 6, 9, and 12 are divisible by 3 ("Fizz"), 5 and 10 are divisible by 5 ("Buzz"), and 15 is divisible by both 3 and 5 ("FizzBuzz"). The rest are printed as is.

Solution

To solve this problem, we'll iterate through all numbers from 1 to n, inclusively. At each iteration, we will evaluate the current number against two conditions: is it a multiple of 3, and is it a multiple of 5? Based on these conditions, we'll decide whether to add the number itself, "Fizz", "Buzz", or "FizzBuzz" to our result list.

This approach works because it directly applies the divisibility rule, ensuring that we correctly categorize each number according to the problem's requirements. It's effective because it's straightforward, avoids unnecessary complexity, and directly maps to the problem's logic.

Step-by-step Algorithm

• Initialize an empty list result to store the output strings.
• Iterate through all numbers from 1 to n (inclusive).
  • For each number, check if it is divisible by both 3 and 5.
    • If true, append "FizzBuzz" to result.
  • Else, check if the number is divisible by 3.
    • If true, append "Fizz" to result.
  • Else, check if the number is divisible by 5.
    • If true, append "Buzz" to result.
  • If none of the above conditions are met, append the string representation of the current number to result.
• Return the result list.

Algorithm Walkthrough

Let's walk through the algorithm with the input n = 16.

1. Start with 1: Not divisible by 3 or 5, output "1".
2. Move to 2: Not divisible by 3 or 5, output "2".
3. At 3: Divisible by 3, output "Fizz".
4. At 4: Not divisible by 3 or 5, output "4".
5. At 5: Divisible by 5, output "Buzz".
6. At 6: Divisible by 3, output "Fizz".
7. At 7: Not divisible by 3 or 5, output "7".
8. At 8: Not divisible by 3 or 5, output "8".
9. At 9: Divisible by 3, output "Fizz".
10. At 10: Divisible by 5, output "Buzz".
11. At 11: Not divisible by 3 or 5, output "11".
12. At 12: Divisible by 3, output "Fizz".
13. At 13: Not divisible by 3 or 5, output "13".
14. At 14: Not divisible by 3 or 5, output "14".
15. At 15: Divisible by both 3 and 5, output "FizzBuzz".
16. At 16: Not divisible by 3 or 5, output "16".

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {

  // Method to solve FizzBuzz
  public List<String> fizzBuzz(int n) {
    List<String> result = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
      if (i % 15 == 0) { // Check for numbers divisible by both 3 and 5
        result.add("FizzBuzz");
      } else if (i % 3 == 0) { // Check for numbers divisible by 3
        result.add("Fizz");
      } else if (i % 5 == 0) { // Check for numbers divisible by 5
        result.add("Buzz");
      } else { // Numbers not divisible by 3 or 5
        result.add(String.valueOf(i));
      }
    }
    return result;
  }

  // Main method to test the fizzBuzz function
  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.fizzBuzz(4)); // Example 1
    System.out.println(solution.fizzBuzz(7)); // Example 2
    System.out.println(solution.fizzBuzz(16)); // Example 3
  }
}

Complexity Analysis

Time Complexity

• : The algorithm iterates once through all numbers from 1 to n, performing a constant amount of work for each number (checking divisibility by 3, 5, and both). Therefore, the time complexity is directly proportional to the input size n.

Space Complexity

• : The space complexity is also linear with respect to the input size n, as we store each result (either "Fizz", "Buzz", "FizzBuzz", or the number itself as a string) in a list (or array, depending on the programming language) that grows with n.