Jobs

Interviews

Discussions

Count Pairs That Form a Complete Day I

Easy

Asked by:

9 views

Topics:

Arrays

Given an integer array hours representing times in hours, return an integer denoting the number of pairs i, j where i < j and hours[i] + hours[j] forms a complete day.

A complete day is defined as a time duration that is an exact multiple of 24 hours.

For example, 1 day is 24 hours, 2 days is 48 hours, 3 days is 72 hours, and so on.

Example 1:

Input: hours = [12,12,30,24,24]

Output: 2

Explanation:

The pairs of indices that form a complete day are (0, 1) and (3, 4).

Example 2:

Input: hours = [72,48,24,3]

Output: 3

Explanation:

The pairs of indices that form a complete day are (0, 1), (0, 2), and (1, 2).

Constraints:

1 <= hours.length <= 100
1 <= hours[i] <= 10⁹

Try coding it in LeetCode

Count Pairs That Form a Complete Day I

Easy

Asked by:

9 views

Topics:

Arrays

Given an integer array hours representing times in hours, return an integer denoting the number of pairs i, j where i < j and hours[i] + hours[j] forms a complete day.

A complete day is defined as a time duration that is an exact multiple of 24 hours.

For example, 1 day is 24 hours, 2 days is 48 hours, 3 days is 72 hours, and so on.

Example 1:

Input: hours = [12,12,30,24,24]

Output: 2

Explanation:

The pairs of indices that form a complete day are (0, 1) and (3, 4).

Example 2:

Input: hours = [72,48,24,3]

Output: 3

Explanation:

The pairs of indices that form a complete day are (0, 1), (0, 2), and (1, 2).

Constraints:

1 <= hours.length <= 100
1 <= hours[i] <= 10⁹

Try coding it in LeetCode

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:

Can you define what constitutes a "complete day"? Is it always 24 hours, or can the definition vary?
What data type will the input array contain, and what are the possible ranges for these values? Can I assume they are integers?
Are there any constraints on the size of the input array? For very large arrays, do you have any performance expectations?
If there are multiple pairs that form a "complete day", should I return all of them, one of them, or the count of such pairs?
What should I return if there are no pairs that form a "complete day"? Should I return 0, null, or throw an exception?

Brute Force Solution

Approach

We are given a collection of numbers and a target value representing a complete day. The brute force method involves checking every possible pair of numbers to see if their combination equals the target value.

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

Take the first number in the collection.
Compare it with every other number in the collection, one at a time.
For each comparison, check if the sum of the two numbers equals the target value representing a complete day.
If the sum equals the target value, we have found a valid pair, so count it.
Move to the second number in the collection and repeat the comparison process with all the remaining numbers.
Continue this process for each number in the collection, ensuring you don't double-count pairs.
The total count of valid pairs is the answer.

Code Implementation

def count_complete_day_pairs_brute_force(numbers, complete_day):
    number_of_valid_pairs = 0

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare the current number with all subsequent numbers
        for second_number_index in range(first_number_index + 1, len(numbers)):
            # Check if the sum equals the target value
            if numbers[first_number_index] + numbers[second_number_index] == complete_day:

                # Increment counter if the pair matches
                number_of_valid_pairs += 1

    return number_of_valid_pairs

Big(O) Analysis

Time Complexity

O(n²) – The provided algorithm iterates through the input array of size n. For each element, it compares it with every subsequent element in the array. In the worst-case scenario, where no optimization is used, the algorithm checks approximately n * (n-1) / 2 pairs of numbers to see if they sum to the target value. This can be approximated as n²/2, and when we drop the constant factor and lower-order terms, the time complexity is O(n²).

Space Complexity

O(1) – The described brute force approach iterates through pairs of numbers within the input collection. It doesn't create any auxiliary data structures like lists, hash maps, or recursion stacks to store intermediate results. It only uses a few constant space variables, such as loop counters and a variable to store the count of pairs. Therefore, the space complexity remains constant regardless of the input size, N, making it O(1).

Optimal Solution

Approach

The challenge is to count pairs of numbers that, when combined in a specific way, form a 'complete' day. Instead of checking every possible pair, which would take a very long time, we can use a clever counting trick. This involves pre-calculating certain values to quickly determine how many pairs satisfy the condition.

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

First, we need to understand what makes a 'complete' day. This depends on how the two numbers are combined based on the problem's definition.
Instead of directly comparing every pair of numbers, let's think about what each number 'needs' to form a complete day.
Create a way to count how many times each 'need' appears in our collection of numbers. We can use something like a tally system.
Once we have this count, we can quickly determine how many pairs make a complete day by matching each number with its corresponding 'need'.
Be careful to avoid counting the same pair twice. This is a potential pitfall that needs to be considered while counting.
Lastly, sum up all the successful matches to get the final count of pairs forming a complete day. This completes our calculation.

Code Implementation

def count_complete_days(numbers):
    day_length = 24
    frequency_count = {}
    pair_count = 0

    for number in numbers:
        if number in frequency_count:
            frequency_count[number] += 1
        else:
            frequency_count[number] = 1

    # Iterate through each number to find its complement
    for number in frequency_count:
        complement = day_length - number
        #Ensure we don't double count the same pair

        if complement in frequency_count:
            if number == complement:
                pair_count += frequency_count[number] * (frequency_count[number] - 1) // 2
            elif number < complement:
                pair_count += frequency_count[number] * frequency_count[complement]

    return pair_count

Big(O) Analysis

Time Complexity

O(n) – The described solution focuses on pre-calculating values and using a tally system. The dominant operation involves iterating through the input collection of n numbers to determine what each number 'needs' to form a complete day and updating the tally. Subsequently, we iterate through the tallies to count successful matches. These steps take time proportional to the size of the input array, n. Therefore, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a tally system to count how many times each 'need' appears in the collection of numbers. This tally system can be implemented using a hash map or an array. In the worst case, each number in the input array has a unique 'need', requiring us to store N counts. Therefore, the auxiliary space used is proportional to the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or undefined input array	Check for null or undefined input at the beginning and return an empty list.
Array with one element	Return an empty list since a pair requires at least two elements.
Array with all elements equal	The hashmap approach should still correctly count pairs without index collisions.
Integer overflow when summing elements	Use a data type with a larger range (e.g., long) to store intermediate sums if necessary.
Extremely large input array size	The hash map approach should provide near O(n) complexity, which is efficient for large arrays.
No pairs sum up to a complete day (24)	The algorithm should naturally return an empty list or a zero count if no pairs meet the condition.
Negative numbers in the array	The solution should handle negative numbers correctly as sums can be negative.
Presence of zero in the input array	Zero will be correctly considered when forming valid pairs with 24 or other numbers to reach 24.

Null or undefined input array

How to Handle:

Check for null or undefined input at the beginning and return an empty list.

Array with one element

How to Handle:

Return an empty list since a pair requires at least two elements.

Array with all elements equal

How to Handle:

The hashmap approach should still correctly count pairs without index collisions.

Integer overflow when summing elements

How to Handle:

Use a data type with a larger range (e.g., long) to store intermediate sums if necessary.

Extremely large input array size

How to Handle:

The hash map approach should provide near O(n) complexity, which is efficient for large arrays.

No pairs sum up to a complete day (24)

How to Handle:

The algorithm should naturally return an empty list or a zero count if no pairs meet the condition.

Negative numbers in the array

How to Handle:

The solution should handle negative numbers correctly as sums can be negative.

Presence of zero in the input array

How to Handle:

Zero will be correctly considered when forming valid pairs with 24 or other numbers to reach 24.

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:

Can you define what constitutes a "complete day"? Is it always 24 hours, or can the definition vary?
What data type will the input array contain, and what are the possible ranges for these values? Can I assume they are integers?
Are there any constraints on the size of the input array? For very large arrays, do you have any performance expectations?
If there are multiple pairs that form a "complete day", should I return all of them, one of them, or the count of such pairs?
What should I return if there are no pairs that form a "complete day"? Should I return 0, null, or throw an exception?

Brute Force Solution

Approach

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

Take the first number in the collection.
Compare it with every other number in the collection, one at a time.
For each comparison, check if the sum of the two numbers equals the target value representing a complete day.
If the sum equals the target value, we have found a valid pair, so count it.
Move to the second number in the collection and repeat the comparison process with all the remaining numbers.
Continue this process for each number in the collection, ensuring you don't double-count pairs.
The total count of valid pairs is the answer.

Code Implementation

def count_complete_day_pairs_brute_force(numbers, complete_day):
    number_of_valid_pairs = 0

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare the current number with all subsequent numbers
        for second_number_index in range(first_number_index + 1, len(numbers)):
            # Check if the sum equals the target value
            if numbers[first_number_index] + numbers[second_number_index] == complete_day:

                # Increment counter if the pair matches
                number_of_valid_pairs += 1

    return number_of_valid_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, we need to understand what makes a 'complete' day. This depends on how the two numbers are combined based on the problem's definition.
Instead of directly comparing every pair of numbers, let's think about what each number 'needs' to form a complete day.
Create a way to count how many times each 'need' appears in our collection of numbers. We can use something like a tally system.
Once we have this count, we can quickly determine how many pairs make a complete day by matching each number with its corresponding 'need'.
Be careful to avoid counting the same pair twice. This is a potential pitfall that needs to be considered while counting.
Lastly, sum up all the successful matches to get the final count of pairs forming a complete day. This completes our calculation.

Code Implementation

def count_complete_days(numbers):
    day_length = 24
    frequency_count = {}
    pair_count = 0

    for number in numbers:
        if number in frequency_count:
            frequency_count[number] += 1
        else:
            frequency_count[number] = 1

    # Iterate through each number to find its complement
    for number in frequency_count:
        complement = day_length - number
        #Ensure we don't double count the same pair

        if complement in frequency_count:
            if number == complement:
                pair_count += frequency_count[number] * (frequency_count[number] - 1) // 2
            elif number < complement:
                pair_count += frequency_count[number] * frequency_count[complement]

    return pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined input array	Check for null or undefined input at the beginning and return an empty list.
Array with one element	Return an empty list since a pair requires at least two elements.
Array with all elements equal	The hashmap approach should still correctly count pairs without index collisions.
Integer overflow when summing elements	Use a data type with a larger range (e.g., long) to store intermediate sums if necessary.
Extremely large input array size	The hash map approach should provide near O(n) complexity, which is efficient for large arrays.
No pairs sum up to a complete day (24)	The algorithm should naturally return an empty list or a zero count if no pairs meet the condition.
Negative numbers in the array	The solution should handle negative numbers correctly as sums can be negative.
Presence of zero in the input array	Zero will be correctly considered when forming valid pairs with 24 or other numbers to reach 24.

Null or undefined input array

How to Handle:

Check for null or undefined input at the beginning and return an empty list.

Array with one element

How to Handle:

Return an empty list since a pair requires at least two elements.

Array with all elements equal

How to Handle:

The hashmap approach should still correctly count pairs without index collisions.

Integer overflow when summing elements

How to Handle:

Use a data type with a larger range (e.g., long) to store intermediate sums if necessary.

Extremely large input array size

How to Handle:

The hash map approach should provide near O(n) complexity, which is efficient for large arrays.

No pairs sum up to a complete day (24)

How to Handle:

The algorithm should naturally return an empty list or a zero count if no pairs meet the condition.

Negative numbers in the array

How to Handle:

The solution should handle negative numbers correctly as sums can be negative.

Presence of zero in the input array

How to Handle:

Zero will be correctly considered when forming valid pairs with 24 or other numbers to reach 24.