Bit Manipulation
Backtracking
Description
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:
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
class Solution :
def readBinaryWatch ( self , turnedOn : int ) -> List [ str ]:
return [
' {:d} : {:02d} ' . format ( i , j )
for i in range ( 12 )
for j in range ( 60 )
if ( bin ( i ) + bin ( j )) . count ( '1' ) == turnedOn
]
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public List < String > readBinaryWatch ( int turnedOn ) {
List < String > ans = new ArrayList <> ();
for ( int i = 0 ; i < 12 ; ++ i ) {
for ( int j = 0 ; j < 60 ; ++ j ) {
if ( Integer . bitCount ( i ) + Integer . bitCount ( j ) == turnedOn ) {
ans . add ( String . format ( "%d:%02d" , i , j ));
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
vector < string > readBinaryWatch ( int turnedOn ) {
vector < string > ans ;
for ( int i = 0 ; i < 12 ; ++ i ) {
for ( int j = 0 ; j < 60 ; ++ j ) {
if ( __builtin_popcount ( i ) + __builtin_popcount ( j ) == turnedOn ) {
ans . push_back ( to_string ( i ) + ":" + ( j < 10 ? "0" : "" ) + to_string ( j ));
}
}
}
return ans ;
}
};
func readBinaryWatch ( turnedOn int ) [] string {
var ans [] string
for i := 0 ; i < 12 ; i ++ {
for j := 0 ; j < 60 ; j ++ {
if bits . OnesCount ( uint ( i )) + bits . OnesCount ( uint ( j )) == turnedOn {
ans = append ( ans , fmt . Sprintf ( "%d:%02d" , i , j ))
}
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 function readBinaryWatch ( turnedOn : number ) : string [] {
if ( turnedOn === 0 ) {
return [ '0:00' ];
}
const n = 10 ;
const res = [];
const bitArr = new Array ( 10 ). fill ( false );
const createTime = () => {
return [
bitArr . slice ( 0 , 4 ). reduce (( p , v ) => ( p << 1 ) | Number ( v ), 0 ),
bitArr . slice ( 4 ). reduce (( p , v ) => ( p << 1 ) | Number ( v ), 0 ),
];
};
const helper = ( i : number , count : number ) => {
if ( i + count > n || count === 0 ) {
return ;
}
bitArr [ i ] = true ;
if ( count === 1 ) {
const [ h , m ] = createTime ();
if ( h < 12 && m < 60 ) {
res . push ( ` ${ h } : ${ m < 10 ? '0' + m : m } ` );
}
}
helper ( i + 1 , count - 1 );
bitArr [ i ] = false ;
helper ( i + 1 , count );
};
helper ( 0 , turnedOn );
return res ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 impl Solution {
fn create_time ( bit_arr : & [ bool ; 10 ]) -> ( i32 , i32 ) {
let mut h = 0 ;
let mut m = 0 ;
for i in 0 .. 4 {
h <<= 1 ;
h |= if bit_arr [ i ] { 1 } else { 0 };
}
for i in 4 .. 10 {
m <<= 1 ;
m |= if bit_arr [ i ] { 1 } else { 0 };
}
( h , m )
}
fn helper ( res : & mut Vec < String > , bit_arr : & mut [ bool ; 10 ], i : usize , count : usize ) {
if i + count > 10 || count == 0 {
return ;
}
bit_arr [ i ] = true ;
if count == 1 {
let ( h , m ) = Self :: create_time ( bit_arr );
if h < 12 && m < 60 {
if m < 10 {
res . push ( format! ( "{}:0{}" , h , m ));
} else {
res . push ( format! ( "{}:{}" , h , m ));
}
}
}
Self :: helper ( res , bit_arr , i + 1 , count - 1 );
bit_arr [ i ] = false ;
Self :: helper ( res , bit_arr , i + 1 , count );
}
pub fn read_binary_watch ( turned_on : i32 ) -> Vec < String > {
if turned_on == 0 {
return vec! [ String :: from ( "0:00" )];
}
let mut res = vec! [];
let mut bit_arr = [ false ; 10 ];
Self :: helper ( & mut res , & mut bit_arr , 0 , turned_on as usize );
res
}
}
Solution 2
Python3 Java C++ Go
class Solution :
def readBinaryWatch ( self , turnedOn : int ) -> List [ str ]:
ans = []
for i in range ( 1 << 10 ):
h , m = i >> 6 , i & 0b111111
if h < 12 and m < 60 and i . bit_count () == turnedOn :
ans . append ( ' {:d} : {:02d} ' . format ( h , m ))
return ans
1
2
3
4
5
6
7
8
9
10
11
12 class Solution {
public List < String > readBinaryWatch ( int turnedOn ) {
List < String > ans = new ArrayList <> ();
for ( int i = 0 ; i < 1 << 10 ; ++ i ) {
int h = i >> 6 , m = i & 0b111111 ;
if ( h < 12 && m < 60 && Integer . bitCount ( i ) == turnedOn ) {
ans . add ( String . format ( "%d:%02d" , h , m ));
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public :
vector < string > readBinaryWatch ( int turnedOn ) {
vector < string > ans ;
for ( int i = 0 ; i < 1 << 10 ; ++ i ) {
int h = i >> 6 , m = i & 0b111111 ;
if ( h < 12 && m < 60 && __builtin_popcount ( i ) == turnedOn ) {
ans . push_back ( to_string ( h ) + ":" + ( m < 10 ? "0" : "" ) + to_string ( m ));
}
}
return ans ;
}
};
func readBinaryWatch ( turnedOn int ) [] string {
var ans [] string
for i := 0 ; i < 1 << 10 ; i ++ {
h , m := i >> 6 , i & 0 b111111
if h < 12 && m < 60 && bits . OnesCount ( uint ( i )) == turnedOn {
ans = append ( ans , fmt . Sprintf ( "%d:%02d" , h , m ))
}
}
return ans
}
GitHub