LeetCode //C - 401. Binary Watch

401. Binary Watch

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

• For example, the below binary watch reads “4:51”.
  
  Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero.

• For example, “01:00” is not valid. It should be “1:00”.

The minute must consist of two digits and may contain a leading zero.

• For example, “10:2” is not valid. It should be “10:02”.
   

Example 1:

Input: turnedOn = 1
Output: [“0:01”,“0:02”,“0:04”,“0:08”,“0:16”,“0:32”,“1:00”,“2:00”,“4:00”,“8:00”]

Example 2:

Input: turnedOn = 9
Output: []

Constraints:

• 0 <= turnedOn <= 10

From: LeetCode
Link: 401. Binary Watch

Solution:

Ideas:

1. Dynamic Resizing:

• I introduced a variable capacity to track the size of the result array. We start with an initial capacity of 10.
• When the number of times exceeds the current capacity, we double the size of the result array using realloc.

2. Safe Memory Allocation:

• The allocation size for each time string is left at 6 since the format h:mm will never exceed 5 characters (e.g., “8:59”) plus the null terminator.

3. Realloc Error Handling (implicit):

• If realloc fails, it returns NULL, but we assume the system has enough memory to handle this allocation. In real-world applications, additional error handling could be added.

Code:

// Helper function to count how many bits are set to 1
int countBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** readBinaryWatch(int turnedOn, int* returnSize) {
    // Start with an initial capacity for the result array
    int capacity = 10;  // Start with a small initial capacity
    char** result = (char**)malloc(capacity * sizeof(char*));
    int count = 0;
    
    // Iterate over hours (0-11) and minutes (0-59)
    for (int h = 0; h < 12; h++) {
        for (int m = 0; m < 60; m++) {
            // If the total number of LEDs turned on matches `turnedOn`
            if (countBits(h) + countBits(m) == turnedOn) {
                // If the result array is full, double its capacity
                if (count >= capacity) {
                    capacity *= 2;
                    result = (char**)realloc(result, capacity * sizeof(char*));
                }
                // Allocate memory for the time string
                result[count] = (char*)malloc(6 * sizeof(char));
                // Format the time into "h:mm"
                sprintf(result[count], "%d:%02d", h, m);
                count++;
            }
        }
    }
    
    *returnSize = count;
    return result;
}