Jobs

Interviews

Discussions

Count Pairs That Form a Complete Day II

Medium

Asked by:

11 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 <= 5 * 10⁵
1 <= hours[i] <= 10⁹

Try coding it in LeetCode

Count Pairs That Form a Complete Day II

Medium

Asked by:

11 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 <= 5 * 10⁵
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:

What are the possible ranges for the numbers representing the hours and minutes? Specifically, what is the minimum and maximum value for each?
If no pairs sum to a number representing a complete day (i.e., hours and minutes), what should I return? Should I return -1 or 0?
Can the input contain duplicate times? If so, how should they be counted towards the total number of pairs that form a complete day?
Are the hours and minutes provided as separate arrays, or as a single array of time objects or a combined representation (e.g., total minutes)? Can you provide an example input?
Is the order of the pair significant? Meaning, does (hour1, minute1) + (hour2, minute2) count as the same pair as (hour2, minute2) + (hour1, minute1), or should both be counted?

Brute Force Solution

Approach

We want to find how many pairs of entries in our data satisfy a specific condition about creating a 'complete day'. The brute force approach is to simply examine every possible pair, one at a time, and check if it meets the condition.

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

Take the first entry from our data.
Compare it with every other entry in the data, including itself.
For each of these comparisons, check if the pair fulfills the 'complete day' condition.
If it does, make a note of it by increasing our count.
Move to the second entry in the data.
Compare it with every other entry in the data, including itself.
Again, for each comparison, check if the 'complete day' condition is met and increase the count if it is.
Continue this process for every entry in the data, comparing it with all other entries.
Once we have gone through all possible pairs, the total count will represent the number of pairs that form a 'complete day'.

Code Implementation

def count_complete_day_pairs_brute_force(data):
    number_of_complete_days = 0

    # Iterate through all possible pairs
    for first_entry_index in range(len(data)):
        for second_entry_index in range(len(data)):

            # This simulates the complete day condition check.
            # Replace this with the actual logic.
            if data[first_entry_index] + data[second_entry_index] >= 10:

                # Check if the pair fulfills the complete day condition
                number_of_complete_days += 1

    return number_of_complete_days

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input data. For each element, it compares it with every other element, resulting in n comparisons per element. This leads to a total of n * n comparisons. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute force approach that iterates through all possible pairs in the input data. It does not explicitly mention the creation of any auxiliary data structures like arrays, hash maps, or sets for storing intermediate results or visited elements. The algorithm appears to primarily use a counter to keep track of the number of pairs that meet the complete day condition and indices to iterate through the input, which occupies constant space. Therefore, the space complexity is O(1) as it does not depend on the input size, N.

Optimal Solution

Approach

This problem asks us to count pairs of numbers from two lists that add up to a power of two. The key is to realize we don't need to check every single pair. We can use a clever counting trick to avoid redundant calculations.

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

First, create a way to quickly count how many times each number appears in the first list.
Then, for each number in the second list, consider what number it needs to be paired with to reach each possible power of two.
For each power of two, check how many times that 'needed' number appears in the first list (using the counts you created earlier).
Add up all those counts. This gives you the number of pairs using that specific number from the second list.
Repeat for every number in the second list.
Finally, add up all the pair counts to get the total number of pairs that sum to a power of two. Be careful to adjust for pairs where the number is identical in both lists. We might have counted these pairs twice.
This approach avoids checking every possible pair directly, saving a lot of time.

Code Implementation

def count_complete_days_ii(first_list, second_list):
    number_counts = {}
    for number in first_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    total_pairs = 0
    for second_list_number in second_list:
        for power_of_two in [2**i for i in range(60)]:
            needed_number = power_of_two - second_list_number

            # Check if the needed number exists in first_list's counts.
            if needed_number in number_counts:

                total_pairs += number_counts[needed_number]

    # Adjust count for possible overcounting from identical lists
    if first_list == second_list:

        identical_pairs_count = 0
        counts = {}
        for number in first_list:
            counts[number] = counts.get(number, 0) + 1
        for number in counts:
            for power_of_two in [2**i for i in range(60)]:
                if number * 2 == power_of_two:

                    # Remove doubled counts if the lists are identical.
                    identical_pairs_count += (counts[number] * (counts[number] - 1)) // 2
        total_pairs -= identical_pairs_count

    # Need to remove pairs counted twice when two lists are identical
    unique_elements_in_both = set(first_list) & set(second_list)

    for element in unique_elements_in_both:
        if first_list.count(element) == 1 and second_list.count(element) == 1:
            for power_of_two in [2**i for i in range(60)]:
                if element * 2 == power_of_two:
                    total_pairs -= 0

    return total_pairs

Big(O) Analysis

Time Complexity

O(n + m * log(max_power_of_two)) – The first step involves counting the occurrences of each number in the first list (size n), which takes O(n) time using a hash map. Then, for each of the m elements in the second list, we iterate through potential powers of two. The number of powers of two we need to consider is logarithmic with respect to the maximum possible power of two (log(max_power_of_two)). Therefore, the time complexity for iterating the second list and finding the required complement in the first list's counts is O(m * log(max_power_of_two)). Combining both operations, the overall time complexity is O(n + m * log(max_power_of_two)).

Space Complexity

O(N) – The primary space complexity comes from the need to store counts of numbers from the first list using a hash map or dictionary. In the worst case, all numbers in the first list are unique, requiring the hash map to store N key-value pairs, where N is the number of elements in the first list. Therefore, the auxiliary space used scales linearly with the input size N. No other significant data structures are used, resulting in an overall space complexity of O(N).

Edge Cases

Case	How to Handle
Empty array input	Return 0 as there are no pairs.
Array with only one element	Return 0 as a pair requires two elements.
Array with two identical elements	Handle correctly using a hashmap or similar structure that allows checking for the existence of an element and its index before counting a pair, preventing double-counting with the same element index.
Very large input array (performance)	Use an efficient algorithm like a hash map with O(n) time complexity for lookup to ensure scalability.
Input array contains only zero values	Correctly handle zero values when calculating the target value for finding pairs.
Input contains extremely large numbers (potential overflow)	Use appropriate data types (e.g., long) to prevent integer overflow when calculating the target or storing counts.
No valid pairs exist in the input	Return 0 if no pairs are found after iterating through all elements.
Array contains negative numbers	The solution should handle negative numbers correctly when determining a target value for pair matching.

Empty array input

How to Handle:

Return 0 as there are no pairs.

Array with only one element

How to Handle:

Return 0 as a pair requires two elements.

Array with two identical elements

How to Handle:

Handle correctly using a hashmap or similar structure that allows checking for the existence of an element and its index before counting a pair, preventing double-counting with the same element index.

Very large input array (performance)

How to Handle:

Use an efficient algorithm like a hash map with O(n) time complexity for lookup to ensure scalability.

Input array contains only zero values

How to Handle:

Correctly handle zero values when calculating the target value for finding pairs.

Input contains extremely large numbers (potential overflow)

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow when calculating the target or storing counts.

No valid pairs exist in the input

How to Handle:

Return 0 if no pairs are found after iterating through all elements.

Array contains negative numbers

How to Handle:

The solution should handle negative numbers correctly when determining a target value for pair matching.

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 are the possible ranges for the numbers representing the hours and minutes? Specifically, what is the minimum and maximum value for each?
If no pairs sum to a number representing a complete day (i.e., hours and minutes), what should I return? Should I return -1 or 0?
Can the input contain duplicate times? If so, how should they be counted towards the total number of pairs that form a complete day?
Are the hours and minutes provided as separate arrays, or as a single array of time objects or a combined representation (e.g., total minutes)? Can you provide an example input?
Is the order of the pair significant? Meaning, does (hour1, minute1) + (hour2, minute2) count as the same pair as (hour2, minute2) + (hour1, minute1), or should both be counted?

Brute Force Solution

Approach

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

Take the first entry from our data.
Compare it with every other entry in the data, including itself.
For each of these comparisons, check if the pair fulfills the 'complete day' condition.
If it does, make a note of it by increasing our count.
Move to the second entry in the data.
Compare it with every other entry in the data, including itself.
Again, for each comparison, check if the 'complete day' condition is met and increase the count if it is.
Continue this process for every entry in the data, comparing it with all other entries.
Once we have gone through all possible pairs, the total count will represent the number of pairs that form a 'complete day'.

Code Implementation

def count_complete_day_pairs_brute_force(data):
    number_of_complete_days = 0

    # Iterate through all possible pairs
    for first_entry_index in range(len(data)):
        for second_entry_index in range(len(data)):

            # This simulates the complete day condition check.
            # Replace this with the actual logic.
            if data[first_entry_index] + data[second_entry_index] >= 10:

                # Check if the pair fulfills the complete day condition
                number_of_complete_days += 1

    return number_of_complete_days

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, create a way to quickly count how many times each number appears in the first list.
Then, for each number in the second list, consider what number it needs to be paired with to reach each possible power of two.
For each power of two, check how many times that 'needed' number appears in the first list (using the counts you created earlier).
Add up all those counts. This gives you the number of pairs using that specific number from the second list.
Repeat for every number in the second list.
Finally, add up all the pair counts to get the total number of pairs that sum to a power of two. Be careful to adjust for pairs where the number is identical in both lists. We might have counted these pairs twice.
This approach avoids checking every possible pair directly, saving a lot of time.

Code Implementation

def count_complete_days_ii(first_list, second_list):
    number_counts = {}
    for number in first_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    total_pairs = 0
    for second_list_number in second_list:
        for power_of_two in [2**i for i in range(60)]:
            needed_number = power_of_two - second_list_number

            # Check if the needed number exists in first_list's counts.
            if needed_number in number_counts:

                total_pairs += number_counts[needed_number]

    # Adjust count for possible overcounting from identical lists
    if first_list == second_list:

        identical_pairs_count = 0
        counts = {}
        for number in first_list:
            counts[number] = counts.get(number, 0) + 1
        for number in counts:
            for power_of_two in [2**i for i in range(60)]:
                if number * 2 == power_of_two:

                    # Remove doubled counts if the lists are identical.
                    identical_pairs_count += (counts[number] * (counts[number] - 1)) // 2
        total_pairs -= identical_pairs_count

    # Need to remove pairs counted twice when two lists are identical
    unique_elements_in_both = set(first_list) & set(second_list)

    for element in unique_elements_in_both:
        if first_list.count(element) == 1 and second_list.count(element) == 1:
            for power_of_two in [2**i for i in range(60)]:
                if element * 2 == power_of_two:
                    total_pairs -= 0

    return total_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array input	Return 0 as there are no pairs.
Array with only one element	Return 0 as a pair requires two elements.
Array with two identical elements	Handle correctly using a hashmap or similar structure that allows checking for the existence of an element and its index before counting a pair, preventing double-counting with the same element index.
Very large input array (performance)	Use an efficient algorithm like a hash map with O(n) time complexity for lookup to ensure scalability.
Input array contains only zero values	Correctly handle zero values when calculating the target value for finding pairs.
Input contains extremely large numbers (potential overflow)	Use appropriate data types (e.g., long) to prevent integer overflow when calculating the target or storing counts.
No valid pairs exist in the input	Return 0 if no pairs are found after iterating through all elements.
Array contains negative numbers	The solution should handle negative numbers correctly when determining a target value for pair matching.

Empty array input

How to Handle:

Return 0 as there are no pairs.

Array with only one element

How to Handle:

Return 0 as a pair requires two elements.

Array with two identical elements

How to Handle:

Very large input array (performance)

How to Handle:

Use an efficient algorithm like a hash map with O(n) time complexity for lookup to ensure scalability.

Input array contains only zero values

How to Handle:

Correctly handle zero values when calculating the target value for finding pairs.

Input contains extremely large numbers (potential overflow)

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow when calculating the target or storing counts.

No valid pairs exist in the input

How to Handle:

Return 0 if no pairs are found after iterating through all elements.

Array contains negative numbers

How to Handle:

The solution should handle negative numbers correctly when determining a target value for pair matching.