Leap Year in Python - Time Complexity: O(1)

A leap year happens every four years, so it's a year that is perfectly divisible by four.

However, if the year is a multiple of 100 (1800, 1900, etc), the year must be divisible by 400 to be leap.

Write a function that determines if the year is a leap year or not.

Examples:

leapYear(2020) ➞ true

leapYear(2021) ➞ false

leapYear(1968) ➞ true

leapYear(1900) ➞ false

Understanding the Problem

The core challenge of this problem is to correctly identify leap years based on the given rules. Leap years are significant in calendar systems and are used to keep our calendar year synchronized with the astronomical year. Misidentifying a leap year can lead to incorrect date calculations.

Common pitfalls include not accounting for the special rule regarding years that are multiples of 100 but not 400.

Approach

To solve this problem, we need to check the divisibility of the given year by 4, 100, and 400. Here's a step-by-step approach:

First, check if the year is divisible by 4. If not, it is not a leap year.
If the year is divisible by 4, check if it is also divisible by 100.
If the year is divisible by 100, then check if it is divisible by 400. If it is, then it is a leap year; otherwise, it is not.
If the year is not divisible by 100, then it is a leap year.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Check if the year is divisible by 4.
If it is not divisible by 4, return False.
If it is divisible by 4, check if it is divisible by 100.
If it is divisible by 100, check if it is divisible by 400.
If it is divisible by 400, return True; otherwise, return False.
If it is not divisible by 100, return True.

Code Implementation

def leapYear(year):
    # Check if the year is divisible by 4
    if year % 4 == 0:
        # Check if the year is divisible by 100
        if year % 100 == 0:
            # Check if the year is divisible by 400
            if year % 400 == 0:
                return True
            else:
                return False
        else:
            return True
    else:
        return False

# Test cases
print(leapYear(2020))  # ➞ true
print(leapYear(2021))  # ➞ false
print(leapYear(1968))  # ➞ true
print(leapYear(1900))  # ➞ false

Complexity Analysis

The time complexity of this solution is O(1) because the number of operations does not depend on the size of the input. The space complexity is also O(1) as we are not using any additional space that scales with the input.

Edge Cases

Potential edge cases include:

Years that are exactly divisible by 100 but not by 400 (e.g., 1900, 2100).
Years that are exactly divisible by 400 (e.g., 1600, 2000).
Years that are not divisible by 4 (e.g., 2019, 2021).

These edge cases are handled by the algorithm as it checks for divisibility by 4, 100, and 400 in the correct order.

Testing

To test the solution comprehensively, we should include a variety of test cases:

Common leap years (e.g., 2020, 2016).
Common non-leap years (e.g., 2019, 2021).
Years divisible by 100 but not 400 (e.g., 1900, 2100).
Years divisible by 400 (e.g., 1600, 2000).

We can use Python's built-in unittest framework to automate these tests.

Thinking and Problem-Solving Tips

When approaching such problems, it is crucial to:

Understand the problem statement and constraints thoroughly.
Break down the problem into smaller, manageable parts.
Consider edge cases and how to handle them.
Write clean, readable code with comments explaining the logic.

Practicing similar problems and studying algorithms can significantly improve problem-solving skills.

Conclusion

In this blog post, we discussed how to determine if a given year is a leap year. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is essential for developing strong problem-solving skills in programming.

We encourage readers to practice and explore further to solidify their understanding.