Binary Watch

                                            
class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> result;
        for(int h = 0; h < 12; ++h) {
            bitset<4> hourBits(h);
            for(int m = 0; m < 60; ++m) {
                bitset<6> minuteBits(m);
                if(hourBits.count() + minuteBits.count() == turnedOn) {
                    string time = to_string(h) + (m < 10 ? ":0" : ":") + to_string(m);
                    result.push_back(time);
                }
            }
        }
        return result;
    }
};

                                            
class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    res.add(String.format("%d:%02d", h, m));
                }
            }
        }
        return res;
    }
}

                                            
class Solution(object):
    def readBinaryWatch(self, turnedOn):
        return ["{0}:{1:02d}".format(h, m) for h in range(12) for m in range(60) if (bin(h) + bin(m)).count('1') == turnedOn]

                                            
public class Solution {
    public IList<string> ReadBinaryWatch(int turnedOn) {
        List<string> result = new List<string>();
        
        for (int hour = 0; hour < 12; hour++) {
            for (int minute = 0; minute < 60; minute++) {
                if (Convert.ToString(hour, 2).Count(c => c == '1') + Convert.ToString(minute, 2).Count(c => c == '1') == turnedOn) {
                    result.Add(hour + ":" + (minute < 10 ? "0" + minute : minute.ToString()));
                }
            }
        }
        
        return result;
    }
}

                                            
/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    const result = [];
    
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m < 60; m++) {
            if (h.toString(2).split('0').join('').length + m.toString(2).split('0').join('').length === turnedOn) {
                result.push(`${h}:${m < 10 ? '0' + m : m}`);
            }
        }
    }
    
    return result;
};

                                            
function readBinaryWatch(turnedOn: number): string[] {
    const result: string[] = [];
    
    for (let i = 0; i < 12; i++) {
        for (let j = 0; j < 60; j++) {
            if (i.toString(2).split('0').join('').length + j.toString(2).split('0').join('').length === turnedOn) {
                result.push(i + ':' + (j < 10 ? '0' + j : j));
            }
        }
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer $turnedOn
     */
    function readBinaryWatch($turnedOn) {
        $result = [];
        for ($h = 0; $h < 12; $h++) {
            for ($m = 0; $m < 60; $m++) {
                if (substr_count(decbin($h) . decbin($m), '1') === $turnedOn) {
                    $result[] = sprintf("%d:%02d", $h, $m);
                }
            }
        }
        return $result;
    }
}

                                            
class Solution {
    func readBinaryWatch(_ turnedOn: Int) -> [String] {
        var result = [String]()
        for i in 0..<12 {
            for j in 0..<60 {
                if i.nonzeroBitCount + j.nonzeroBitCount == turnedOn {
                    result.append("\(i):" + String(format: "%02d", j))
                }
            }
        }
        return result
    }
}

                                            
class Solution {
    fun readBinaryWatch(turnedOn: Int): List<String> {
        val result = mutableListOf<String>()
        for (i in 0 until 12) {
            for (j in 0 until 60) {
                if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
                    result.add("$i:${if (j < 10) "0$j" else j}")
                }
            }
        }
        return result
    }
}

                                            
class Solution {
  List<String> readBinaryWatch(int turnedOn) {
    List<String> result = [];

    for (int h = 0; h < 12; h++) {
      for (int m = 0; m < 60; m++) {
        if (h.toRadixString(2).split('1').length - 1 + m.toRadixString(2).split('1').length - 1 == turnedOn) {
          result.add('$h:${m < 10 ? '0$m' : m}');
        }
      }
    }

    return result;
  }
}

                                            
func readBinaryWatch(turnedOn int) []string {
    result := []string{}
    for i := 0; i < 12; i++ {
        for j := 0; j < 60; j++ {
            if countBits(i)+countBits(j) == turnedOn {
                result = append(result, fmt.Sprintf("%d:%02d", i, j))
            }
        }
    }
    return result
}

func countBits(num int) int {
    count := 0
    for num > 0 {
        count += num & 1
        num >>= 1
    }
    return count
}

                                            
# @param {Integer} turned_on
# @return {String[]}
def read_binary_watch(turned_on)
    result = []
    (0..11).each do |h|
        (0..59).each do |m|
            if h.to_s(2).count("1") + m.to_s(2).count("1") == turned_on
                result << "#{h}:#{m.to_s.rjust(2, "0")}"
            end
        end
    end
    result
end

                                            
object Solution {
    def readBinaryWatch(turnedOn: Int): List[String] = {
        (0 to 11).flatMap(h => (0 to 59).filter(m => Integer.bitCount(h) + Integer.bitCount(m) == turnedOn).map(m => s"$h:${if (m < 10) "0" else ""}$m")).toList
    }
}

To solve this coding challenge, we need to determine all possible times that a binary watch could display given a certain number of LEDs that are turned on. We should generate all possible combinations of hours and minutes, then filter the combinations where the total number of '1' bits in the binary representation of the hours and minutes equals the given

turnedOn

value.

Explanation

A binary watch has two parts: hours and minutes. The hours part is represented by 4 LEDs, and the minutes part is represented by 6 LEDs. This means the maximum possible hour value is 11 (binary

1011

) and the maximum possible minutes value is 59 (binary

111011

). We need to consider:

Valid hour ranges : 0 to 11.
Valid minute ranges : 0 to 59.
Counting the number of LEDs that are turned on : This can be done using the binary representation of the numbers. For instance, the number of '1' bits in the binary representation of 5 (
101

) is 2.

The task is to find all valid combinations of hours and minutes where the sum of '1' bits in their binary representations equals the given

turnedOn

value.

Step-by-Step Explanation

Generate all possible hour values : Loop over the range from 0 to 11.
Generate all possible minute values : Loop over the range from 0 to 59.
Combine hour and minute values : For each hour value, iterate through all minute values.
Check the number of '1' bits : Convert both hour and minute values to their binary representation. Sum the number of '1' bits in both representations. If this sum equals
turnedOn

, it is a valid time.
Format valid times : Hours should not have leading zeros, but minutes should always be two digits.
Return the formatted valid times .

Detailed Steps in Pseudocode

                                            
# Function to find all possible times on a binary watch
Function possibleBinaryWatchTimes(turnedOn):
# Initialize an empty list to store valid times
validTimes = []

# Loop through all possible hour values (0 to 11)
For hour in range from 0 to 11:
# Loop through all possible minute values (0 to 59)
For minute in range from 0 to 59:
# Calculate the number of '1' bits in the binary representation of hour and minute
totalOnLEDs = countOneBits(hour) + countOneBits(minute)

# Check if the total number of '1' bits matches the turnedOn value
If totalOnLEDs == turnedOn:
# Format the time string, ensuring minutes are two digits
timeString = formatTime(hour, minute)

# Add the formatted time to the list of valid times
validTimes.append(timeString)

# Return the list of valid times
Return validTimes

# Helper function to count the number of '1' bits in the binary representation of an integer
Function countOneBits(number):
# Convert the number to its binary representation
binaryRepresentation = convertToBinary(number)

# Count and return the number of '1' bits in the binary representation
Return countCharacters(binaryRepresentation, '1')

# Helper function to format the time string
Function formatTime(hour, minute):
# Format the time string with hour and minute, ensuring minute is always two digits
Return concatenate(hour, ":", formatWithLeadingZeros(minute, 2))

Here,

convertToBinary

is a pseudocode placeholder for a function that converts an integer to its binary string representation, and

countCharacters

counts occurrences of a specific character in a string. The

formatWithLeadingZeros

ensures the minutes part always has two digits.

Explanation of Constraints and Edge Cases

0 LEDs turned on (
turnedOn = 0

) : The only valid time is "0:00".
Maximum LEDs turned on (
turnedOn = 10

) : No valid times exist because there are only 10 LEDs (4 for hours and 6 for minutes), and all cannot be on at the same time.
Handling leading zeros : Ensure that minutes have leading zeros but hours do not.
Output in any order : The result list need not be sorted.

By following this method and detailed pseudocode, we can systematically solve the problem and generate the correct list of times based on the number of LEDs turned on. This approach ensures we cover all valid intervals and account for the binary representations and constraints properly.