search

interview-preparation / what-we-do

0 stars 8 forks source link

[Hard] interview questions #9 #162

Closed rygh4775 closed 5 years ago

rygh4775 commented 5 years ago

Kth Multiple: 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.

GyuminLee commented 5 years ago

Approach

  1. Brute force
    • 모든 경우의 수 계산 후 sort 하여서 k번째 return. O(n^3 log n) (n3 -> possible combination, n^3 log(n^3) -> sorting) 왜 이렇게 되는지..
  2. Dynamic Programming 처럼 전에 나왔던 수를 이용.

Solution

  1. Improved
    • 3,5,7 * 전에 나왔던 수 를 이용. O(n^2) 왜? image
  2. Optimal
    • 1번에 비해 비교작업을 적게 할 방법 (e.g., 3 7이 있을때 335는 할 필요가 없다)

image 위의 알고리즘으로 코드를 짜면.. image