Category: Java

Posted on by

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: []

Solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();

        // Iterate over possible hours (0 to 11)
        for (int hour = 0; hour < 12; hour++) {
            // Iterate over possible minutes (0 to 59)
            for (int minute = 0; minute < 60; minute++) {
                // Count the number of bits turned on
                int bitsOn = Integer.bitCount(hour) + Integer.bitCount(minute);
                
                // If the total bits on matches the turnedOn count
                if (bitsOn == turnedOn) {
                    // Format the time as "H:MM"
                    result.add(String.format("%d:%02d", hour, minute));
                }
            }
        }
        return result;
    }
}
Posted on by

Letter Combinations of a phone number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Java Solution

class Solution {
     public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        Map<Character, String> digitToLetters = new HashMap<>();
        digitToLetters.put('2', "abc");
        digitToLetters.put('3', "def");
        digitToLetters.put('4', "ghi");
        digitToLetters.put('5', "jkl");
        digitToLetters.put('6', "mno");
        digitToLetters.put('7', "pqrs");
        digitToLetters.put('8', "tuv");
        digitToLetters.put('9', "wxyz");

        List<String> result = new ArrayList<>();
        backtrack(digits, 0, new StringBuilder(), result, digitToLetters);
        return result;
    }

    private void backtrack(String digits, int index, StringBuilder path, List<String> result, Map<Character, String> digitToLetters) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }

        char digit = digits.charAt(index);
        String letters = digitToLetters.get(digit);
        for (char letter : letters.toCharArray()) {
            path.append(letter);
            backtrack(digits, index + 1, path, result, digitToLetters);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

C++ Solution

//
// Created by robert on 12/20/24.
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
void backtrack(string & digits, const int index, string & current, vector<string> & result, const unordered_map<char,string> & map) {
  if (digits.length() == index) {
    result.push_back(current);
    return;
  }
   char digit = digits[index];
   string letters = map.find(digit)->second;
   for( char letter : letters ) {
        current.push_back(letter);
        backtrack( digits, index+1, current, result, map );
        current.pop_back();
   }

}
vector<string> letterCombinations(string digits) {
    vector<string> result;
    string current;

    if (digits.empty()) return result;

    unordered_map<char, string> map;

    map.insert(make_pair('2', "abc"));
    map.insert(make_pair('3', "def"));
    map.insert(make_pair('4', "ghi"));
    map.insert(make_pair('5', "jkl"));
    map.insert(make_pair('6', "mno"));
    map.insert(make_pair('7', "pqrs"));
    map.insert(make_pair('8', "tuv"));
    map.insert(make_pair('9', "wxyz"));


    backtrack(digits, 0, current,  result, map);
    return result;

}

int main(){
    vector<string> result = letterCombinations("23");
    for (const auto & i : result) {
      cout << i << endl;
    }
}