Tìm số lập phương lớn nhất bằng cách xóa ít chữ số nhất từ một số trong Python

Cho một số N, ta cần xác định số lập phương hoàn hảo lớn nhất có thể tạo ra bằng cách xóa tối thiểu các chữ số (có thể không xóa) từ số đó. Ta có thể xóa bất kỳ chữ số nào từ số đã cho. Như ta biết, một số N được gọi là lập phương hoàn hảo nếu N = M³ với M là số nguyên.

Ví dụ, nếu đầu vào là 806, kết quả sẽ là 8, vì ta có thể xóa 0 và 6 để được 8, đây là lập phương của 2.

Thuật toán giải quyết

• Định nghĩa hàm preProcess(n):
  • Tạo danh sách temp_cubes rỗng.
  • Với i từ 1 đến ceil(n^(1/3)):
    • Tính cube = i³.
    • Chuyển cube thành chuỗi cubeString.
    • Thêm cubeString vào temp_cubes.
  • Trả về temp_cubes.
• Định nghĩa hàm solve(num, temp_cubes):
  • Đảo ngược temp_cubes.
  • totalCubes := len(temp_cubes).
  • Với i từ 0 đến totalCubes - 1:
    • temp := temp_cubes[i].
    • digitsInCube := len(temp), index := 0.
    • digitsInNumber := len(num).
    • Với j từ 0 đến digitsInNumber - 1:
      • Nếu num[j] == temp[index] thì index += 1.
      • Nếu digitsInCube == index thì trả về temp.
  • Trả về "Not Possible".
• Từ hàm chính:
  • temp_cubes := preProcess(n).
  • num := str(n).
  • ans := solve(num, temp_cubes).
  • Trả về ans.

Ví dụ minh họa

import math

def preProcess(n):
    temp_cubes = []
    for i in range(1, math.ceil(n ** (1. / 3.))):
        cube = i ** 3
        cubeString = str(cube)
        temp_cubes.append(cubeString)
    return temp_cubes

def solve(num, temp_cubes):
    temp_cubes = temp_cubes[::-1]
    totalCubes = len(temp_cubes)
    for i in range(totalCubes):
        temp = temp_cubes[i]
        digitsInCube = len(temp)
        index = 0
        digitsInNumber = len(num)
        for j in range(digitsInNumber):
            if num[j] == temp[index]:
                index += 1
            if digitsInCube == index:
                return temp
    return "Not Possible"

def getLargestCube(n):
    temp_cubes = preProcess(n)
    num = str(n)
    ans = solve(num, temp_cubes)
    return ans

n = 806
print(getLargestCube(n))  # 8

Đầu vào

806

Đầu ra

8