Count Pairs That Form a Complete Day II solution and explanation
Google
9 more videos on this problem
3185. & 3184 Count Pairs That Form a Complete Day II | Same as Two Sum | Modulo OperationAryan Mittal · 11:42 · 3K views
LeetCode 3185 | Count Pairs That Form a Complete Day II | Weekly Contest 402 | #leetcodecontest #dsaAlgo Horizon · 11:43 · 853 views
3185. Count Pairs That Form a Complete Day II (Leetcode Medium)Programming Live with Larry · 6:32 · 383 views
100301 Count Pairs That Form a Complete Day II | leetcode || contest 402 || solved || java ||Ssquare · 2:14 · 323 views
3185. Count Pairs That Form a Complete Day II | Hashing | ModTech Courses · 10:47 · 299 views
Count Pairs That Form a Complete Day II | LeetCode weekly-contest-402Developer Coder · 8:10 · 245 views
leetcode 3185 Count Pairs That Form a Complete Day IICoder on A Farm · 5:06 · 66 views
Count Pairs That Form a Complete Day |Leetcode Contest 402| Leetcode 3185 |Leetcode 3184 | MAANGCode Thoughts · 4:28 · 66 views
3185. Count Pairs That Form a Complete Day IIgu shanhao · 2:50 · 5 views
Leetcode Weekly contest 402 | Count Pairs That Form a Complete Day I and II | ExplainationWiseCoder · 25:05 · 267 views
The problem
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 * 1051 <= hours[i] <= 109
Approach overview
Problem Overview: You are given an array hours where each value represents time spent on a task. Two indices form a valid pair if the total hours add up to a complete day, meaning (hours[i] + hours[j]) % 24 == 0. The goal is to count how many such pairs exist in the array.
Approach 1: Brute Force Pair Checking (O(n²) time, O(1) space)
The simplest method checks every pair of indices using two nested loops. For each i, iterate through j > i and compute (hours[i] + hours[j]) % 24. If the result equals 0, increment the pair count. This approach requires no additional data structures and directly follows the problem definition. However, it performs n(n-1)/2 comparisons, which becomes expensive for large arrays. Use this approach only for small inputs or as a baseline when validating more optimized logic.
Approach 2: Optimized Remainder Counting with Hash Map (O(n) time, O(1) space)
A more efficient approach relies on modular arithmetic. Instead of comparing every pair, compute remainder = hours[i] % 24. For a pair to form a complete day, the second value must contribute (24 - remainder) % 24. Maintain a frequency map that tracks how many times each remainder has appeared so far. For each element, check how many previously seen values match the required complement remainder and add that count to the result.
This works because if two numbers sum to a multiple of 24, their remainders modulo 24 must complement each other. For example, remainder 5 pairs with 19, 8 pairs with 16, and 0 pairs with another 0. The algorithm processes the array once, performing constant-time hash lookups and updates. Since the remainder range is only 0–23, the map size never exceeds 24 entries.
This technique combines ideas from array traversal and frequency counting using a hash table. It is a common pattern in modular pair problems and falls under the broader category of counting techniques used to avoid quadratic comparisons.
Recommended for interviews: Start by explaining the brute force solution to demonstrate understanding of the pairing condition. Then transition to the remainder-counting strategy. Interviewers expect the O(n) hash map approach because it eliminates redundant comparisons and shows comfort with modular arithmetic and frequency maps.
Approach 1: Brute Force Approach
This is a straightforward approach where you iterate over all possible pairs in the array and check if their sum is a multiple of 24. Although not optimal, it's the simplest solution to understand the problem and attempt manual calculations for small inputs.
def count_complete_days(hours):
count = 0
for i in range(len(hours)):
for j in range(i + 1, len(hours)):
if (hours[i] + hours[j]) % 24 == 0:
count += 1
return count
hours = [12, 12, 30, 24, 24]
print(count_complete_days(hours))public class CompleteDays {
public static int countCompleteDays(int[] hours) {
int count = 0;
for (int i = 0; i < hours.length; i++) {
for (int j = i + 1; j < hours.length; j++) {
if ((hours[i] + hours[j]) % 24 == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] hours = {12, 12, 30, 24, 24};
System.out.println(countCompleteDays(hours));
}
}#include <iostream>
#include <vector>
int countCompleteDays(const std::vector<int>& hours) {
int count = 0;
for (size_t i = 0; i < hours.size(); ++i) {
for (size_t j = i + 1; j < hours.size(); ++j) {
if ((hours[i] + hours[j]) % 24 == 0) {
++count;
}
}
}
return count;
}
int main() {
std::vector<int> hours = {12, 12, 30, 24, 24};
std::cout << countCompleteDays(hours) << std::endl;
return 0;
}function countCompleteDays(hours) {
let count = 0;
for (let i = 0; i < hours.length; i++) {
for (let j = i + 1; j < hours.length; j++) {
if ((hours[i] + hours[j]) % 24 === 0) {
count++;
}
}
}
return count;
}
const hours = [12, 12, 30, 24, 24];
console.log(countCompleteDays(hours));#include <stdio.h>
int countCompleteDays(int* hours, int hoursSize) {
int count = 0;
for (int i = 0; i < hoursSize; i++) {
for (int j = i + 1; j < hoursSize; j++) {
if ((hours[i] + hours[j]) % 24 == 0) {
count++;
}
}
}
return count;
}
int main() {
int hours[] = {12, 12, 30, 24, 24};
int size = sizeof(hours) / sizeof(hours[0]);
printf("%d\n", countCompleteDays(hours, size));
return 0;
}using System;
public class CompleteDays {
public static int CountCompleteDays(int[] hours) {
int count = 0;
for (int i = 0; i < hours.Length; i++) {
for (int j = i + 1; j < hours.Length; j++) {
if ((hours[i] + hours[j]) % 24 == 0) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] hours = {12, 12, 30, 24, 24};
Console.WriteLine(CountCompleteDays(hours));
}
}This Python implementation involves iterating over every pair of elements in hours. It checks if their sum is divisible by 24. The time complexity is O(n^2) due to the double loop, with no additional space usage beyond constant storage (O(1) space complexity).
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Optimized Approach Using Hash Map
This approach optimizes the search for pairs whose sums are multiples of 24 by using a hash map (or dictionary) to track previously seen remainders when each hour is divided by 24. This reduces time complexity to linear.
def count_complete_days(hours):
count = 0
remainder_count = [0] * 24
for h in hours:
remainder = h % 24
complement = (24 - remainder) % 24
count += remainder_count[complement]
remainder_count[remainder] += 1
return count
hours = [12, 12, 30, 24, 24]
print(count_complete_days(hours))import java.util.HashMap;
public class CompleteDays {
public static int countCompleteDays(int[] hours) {
int count = 0;
int[] remainderCount = new int[24];
for (int hour : hours) {
int remainder = hour % 24;
int complement = (24 - remainder) % 24;
count += remainderCount[complement];
remainderCount[remainder]++;
}
return count;
}
public static void main(String[] args) {
int[] hours = {12, 12, 30, 24, 24};
System.out.println(countCompleteDays(hours));
}
}#include <iostream>
#include <vector>
int countCompleteDays(const std::vector<int>& hours) {
int count = 0;
std::vector<int> remainderCount(24, 0);
for (int h : hours) {
int remainder = h % 24;
int complement = (24 - remainder) % 24;
count += remainderCount[complement];
remainderCount[remainder]++;
}
return count;
}
int main() {
std::vector<int> hours = {12, 12, 30, 24, 24};
std::cout << countCompleteDays(hours) << std::endl;
return 0;
}function countCompleteDays(hours) {
let count = 0;
let remainderCount = new Array(24).fill(0);
hours.forEach(hour => {
let remainder = hour % 24;
let complement = (24 - remainder) % 24;
count += remainderCount[complement];
remainderCount[remainder]++;
});
return count;
}
const hours = [12, 12, 30, 24, 24];
console.log(countCompleteDays(hours));#include <stdio.h>
#include <stdlib.h>
int countCompleteDays(int* hours, int hoursSize) {
int count = 0;
int remainderCount[24] = {0};
for (int i = 0; i < hoursSize; i++) {
int remainder = hours[i] % 24;
int complement = (24 - remainder) % 24;
count += remainderCount[complement];
remainderCount[remainder]++;
}
return count;
}
int main() {
int hours[] = {12, 12, 30, 24, 24};
int size = sizeof(hours) / sizeof(hours[0]);
printf("%d\n", countCompleteDays(hours, size));
return 0;
}using System;
public class CompleteDays {
public static int CountCompleteDays(int[] hours) {
int count = 0;
int[] remainderCount = new int[24];
foreach (int hour in hours) {
int remainder = hour % 24;
int complement = (24 - remainder) % 24;
count += remainderCount[complement];
remainderCount[remainder]++;
}
return count;
}
public static void Main() {
int[] hours = {12, 12, 30, 24, 24};
Console.WriteLine(CountCompleteDays(hours));
}
}In this Python solution, a list remainder_count of size 24 tracks the frequency of remainders. For each hour, it finds the complement remainder that would make the sum a multiple of 24. The solution effectively counts these pairs in O(n) time.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Counting
We can use a hash table or an array cnt of length 24 to record the occurrence count of each hour modulo 24.
Iterate through the array hours. For each hour x, we can find the number that, when added to x, results in a multiple of 24, and after modulo 24, this number is (24 - x bmod 24) bmod 24. We then accumulate the occurrence count of this number from the hash table or array. After that, we increment the occurrence count of x modulo 24 by one.
After iterating through the array hours, we can obtain the number of index pairs that meet the problem requirements.
The time complexity is O(n), where n is the length of the array hours. The space complexity is O(C), where C=24.
function countCompleteDayPairs(hours: number[]): number {
const cnt: number[] = Array(24).fill(0);
let ans: number = 0;
for (const x of hours) {
ans += cnt[(24 - (x % 24)) % 24];
++cnt[x % 24];
}
return ans;
}func countCompleteDayPairs(hours []int) (ans int64) {
cnt := [24]int{}
for _, x := range hours {
ans += int64(cnt[(24-x%24)%24])
cnt[x%24]++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach Using Hash Map | Time Complexity: O(n) |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Useful for small inputs or verifying correctness during development |
| Hash Map Remainder Counting | O(n) | O(1) | Best general solution; processes array once using remainder complements |
Frequently asked questions
Is Count Pairs That Form a Complete Day II easy or hard?
The problem is classified as Medium because the brute force idea is simple but recognizing the modular arithmetic optimization requires pattern recognition. Once you apply the remainder counting technique, the implementation becomes straightforward.
Count Pairs That Form a Complete Day II Python/Java solution
Python and Java implementations both follow the same logic: compute hours[i] % 24, look up the complement remainder in a map, add its frequency to the answer, and update the remainder count. The algorithm runs in O(n) time and uses at most 24 entries in the map.
How to solve Count Pairs That Form a Complete Day II in O(n)?
Iterate through the array and compute remainder = hours[i] % 24. Determine the complement remainder needed to reach a multiple of 24 using (24 - remainder) % 24. Add the frequency of that complement from a hash map to the result, then update the current remainder count. This single pass counts all valid pairs in O(n) time.
What is the best approach for Count Pairs That Form a Complete Day II?
The optimal approach uses remainder counting with a hash map. Compute hours[i] % 24 for each element and look for its complement (24 - remainder) % 24 among previously seen values. This reduces the complexity from O(n²) to O(n) while using constant space because only 24 possible remainders exist.
Is Count Pairs That Form a Complete Day II asked at Google/Amazon/Meta?
Problems involving modular pair counting and hash maps are common interview patterns at companies like Google, Amazon, and Meta. While this exact problem may vary, the technique of using remainder complements to detect valid pairs appears frequently in coding interviews.
What data structure is used in Count Pairs That Form a Complete Day II?
The optimized solution uses a hash table (or frequency array) to store counts of remainders modulo 24. This allows constant-time lookup of how many previous values can pair with the current value to form a complete day.
What is the time complexity of Count Pairs That Form a Complete Day II?
The brute force method runs in O(n²) time because every pair of indices is checked. The optimized solution runs in O(n) time by processing the array once and using constant-time hash lookups for complementary remainders.