LeastNumOfCubes

Hôm nay, Nâm được học bài về số lập phương. Nâm ghi nhớ là lập phương của một số n có nghĩa là nhân 3 lần giá trị của nó với nhau: n3 = n × n × n. Sau buổi học, thầy giáo giao bài tập cho cả lớp:

Cho một số nguyên dương n, tìm số lượng ít nhất các số lập phương (27, 64, 125, …) mà tổng của nó bằng n

Bài toán khó quá!! Hãy giúp cậu bé giải nó để kiếm điểm 10 nhé.

Ví dụ:

• Với n = 496 thì kết quả leastNumOfCubes(496) = 3
  • Giải thích: Ta có 2 cách
    • 64 + 216 + 216 = 4³ + 6³ + 6³ = 496
    • 1 + 9 + 125 + 343 = 1³ + 3³ + 5³ + 7³ = 496
    • Nhưng cách ngắn nhất là dùng 3 số 64, 216, 216

• Với n = 8 thì leastNumOfCubes(8) = 1

Đầu vào/ Đầu ra:

• [Giới hạn thời gian chạy] 0.5 giây đối với C++, 3 giây với Java và C#, 4 giây với Python, Go và JavaScript.

• [Đầu vào] Integer n
  1 ≤ n ≤ 105

• [Đầu ra] Integer
  Số lượng ít nhất các số lập phương mà tổng của nó bằng n.