Description
Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7. Note that 3, 5, and 7 do not have to be factors, but it should not have any other prime factors. For example, the first several multiples would be (in order) 1, 3, 5, 7, 9, 15, 21.
Example 1:
Input: k = 5
Output: 9
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C Swift
class Solution :
def getKthMagicNumber ( self , k : int ) -> int :
h = [ 1 ]
vis = { 1 }
for _ in range ( k - 1 ):
cur = heappop ( h )
for f in ( 3 , 5 , 7 ):
if ( nxt := cur * f ) not in vis :
vis . add ( nxt )
heappush ( h , nxt )
return h [ 0 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
private static final int [] FACTORS = new int [] { 3 , 5 , 7 };
public int getKthMagicNumber ( int k ) {
PriorityQueue < Long > q = new PriorityQueue <> ();
Set < Long > vis = new HashSet <> ();
q . offer ( 1L );
vis . add ( 1L );
while ( -- k > 0 ) {
long cur = q . poll ();
for ( int f : FACTORS ) {
long nxt = cur * f ;
if ( ! vis . contains ( nxt )) {
q . offer ( nxt );
vis . add ( nxt );
}
}
}
long ans = q . poll ();
return ( int ) ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
const vector < int > factors = { 3 , 5 , 7 };
int getKthMagicNumber ( int k ) {
priority_queue < long , vector < long > , greater < long >> q ;
unordered_set < long > vis ;
q . push ( 1l );
vis . insert ( 1l );
for ( int i = 0 ; i < k - 1 ; ++ i ) {
long cur = q . top ();
q . pop ();
for ( int f : factors ) {
long nxt = cur * f ;
if ( ! vis . count ( nxt )) {
vis . insert ( nxt );
q . push ( nxt );
}
}
}
return ( int ) q . top ();
}
};
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 func getKthMagicNumber ( k int ) int {
q := hp {[] int { 1 }}
vis := map [ int ] bool { 1 : true }
for i := 0 ; i < k - 1 ; i ++ {
cur := heap . Pop ( & q ).( int )
for _ , f := range [] int { 3 , 5 , 7 } {
nxt := cur * f
if ! vis [ nxt ] {
vis [ nxt ] = true
heap . Push ( & q , nxt )
}
}
}
return q . IntSlice [ 0 ]
}
type hp struct { sort . IntSlice }
func ( h * hp ) Push ( v any ) { h . IntSlice = append ( h . IntSlice , v .( int )) }
func ( h * hp ) Pop () any {
a := h . IntSlice
v := a [ len ( a ) - 1 ]
h . IntSlice = a [: len ( a ) - 1 ]
return v
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 function getKthMagicNumber ( k : number ) : number {
const dp = [ 1 ];
const index = [ 0 , 0 , 0 ];
while ( dp . length < k ) {
const a = dp [ index [ 0 ]] * 3 ;
const b = dp [ index [ 1 ]] * 5 ;
const c = dp [ index [ 2 ]] * 7 ;
const num = Math . min ( a , b , c );
dp . push ( num );
if ( a === num ) {
index [ 0 ] ++ ;
}
if ( b === num ) {
index [ 1 ] ++ ;
}
if ( c === num ) {
index [ 2 ] ++ ;
}
}
return dp [ k - 1 ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 impl Solution {
pub fn get_kth_magic_number ( k : i32 ) -> i32 {
let k = k as usize ;
let mut dp = vec! [ 1 ];
let mut index = [ 0 , 0 , 0 ];
for _ in 1 .. k {
let a = dp [ index [ 0 ]] * 3 ;
let b = dp [ index [ 1 ]] * 5 ;
let c = dp [ index [ 2 ]] * 7 ;
let num = a . min ( b . min ( c ));
dp . push ( num );
if a == num {
index [ 0 ] += 1 ;
}
if b == num {
index [ 1 ] += 1 ;
}
if c == num {
index [ 2 ] += 1 ;
}
}
dp [ k - 1 ]
}
}
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 #define min(a, b) (((a) < (b)) ? (a) : (b))
int getKthMagicNumber ( int k ) {
int * dp = ( int * ) malloc ( sizeof ( int ) * k );
dp [ 0 ] = 1 ;
int index [ 3 ] = { 0 , 0 , 0 };
for ( int i = 1 ; i < k ; i ++ ) {
int a = dp [ index [ 0 ]] * 3 ;
int b = dp [ index [ 1 ]] * 5 ;
int c = dp [ index [ 2 ]] * 7 ;
int num = min ( a , min ( b , c ));
dp [ i ] = num ;
if ( a == num ) {
index [ 0 ] ++ ;
}
if ( b == num ) {
index [ 1 ] ++ ;
}
if ( c == num ) {
index [ 2 ] ++ ;
}
}
int res = dp [ k - 1 ];
free ( dp );
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 class Solution {
private let factors = [ 3 , 5 , 7 ]
func getKthMagicNumber ( _ k : Int ) -> Int {
var heap : [ Int ] = [ 1 ]
var seen = Set < Int >()
seen . insert ( 1 )
var value = 1
for _ in 1. .. k {
value = heap . removeFirst ()
for factor in factors {
let nextValue = value * factor
if ! seen . contains ( nextValue ) {
heap . append ( nextValue )
seen . insert ( nextValue )
}
}
heap . sort ()
}
return value
}
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution :
def getKthMagicNumber ( self , k : int ) -> int :
dp = [ 1 ] * ( k + 1 )
p3 = p5 = p7 = 1
for i in range ( 2 , k + 1 ):
a , b , c = dp [ p3 ] * 3 , dp [ p5 ] * 5 , dp [ p7 ] * 7
v = min ( a , b , c )
dp [ i ] = v
if v == a :
p3 += 1
if v == b :
p5 += 1
if v == c :
p7 += 1
return dp [ k ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public int getKthMagicNumber ( int k ) {
int [] dp = new int [ k + 1 ] ;
Arrays . fill ( dp , 1 );
int p3 = 1 , p5 = 1 , p7 = 1 ;
for ( int i = 2 ; i <= k ; ++ i ) {
int a = dp [ p3 ] * 3 , b = dp [ p5 ] * 5 , c = dp [ p7 ] * 7 ;
int v = Math . min ( Math . min ( a , b ), c );
dp [ i ] = v ;
if ( v == a ) {
++ p3 ;
}
if ( v == b ) {
++ p5 ;
}
if ( v == c ) {
++ p7 ;
}
}
return dp [ k ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public :
int getKthMagicNumber ( int k ) {
vector < int > dp ( k + 1 , 1 );
int p3 = 1 , p5 = 1 , p7 = 1 ;
for ( int i = 2 ; i <= k ; ++ i ) {
int a = dp [ p3 ] * 3 , b = dp [ p5 ] * 5 , c = dp [ p7 ] * 7 ;
int v = min ( min ( a , b ), c );
dp [ i ] = v ;
if ( v == a ) {
++ p3 ;
}
if ( v == b ) {
++ p5 ;
}
if ( v == c ) {
++ p7 ;
}
}
return dp [ k ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func getKthMagicNumber ( k int ) int {
dp := make ([] int , k + 1 )
dp [ 1 ] = 1
p3 , p5 , p7 := 1 , 1 , 1
for i := 2 ; i <= k ; i ++ {
a , b , c := dp [ p3 ] * 3 , dp [ p5 ] * 5 , dp [ p7 ] * 7
v := min ( min ( a , b ), c )
dp [ i ] = v
if v == a {
p3 ++
}
if v == b {
p5 ++
}
if v == c {
p7 ++
}
}
return dp [ k ]
}
