หาเลขยกกำลังสามมากที่สุดจากการลบหลักสัมประสิทธิ์น้อยที่สุดใน Python

หา Cube มากที่สุดที่ได้จากการลบหลักของตัวเลข

กำหนดตัวเลข N ต้องการหาเลขยกกำลังสาม (Perfect Cube) ที่ใหญ่ที่สุดซึ่งสามารถสร้างได้โดยการลบหลักสัมประสิทธิ์ (Digits) ออกจาก N น้อยที่สุด (อาจลบ 0 หลัก) เลขยกกำลังสามคือตัวเลขที่เขียนในรูป M³ สำหรับจำนวนเต็ม M

ตัวอย่าง: N = 806 → ลบ 0 และ 6 ได้ 8 ซึ่งเป็น 2³ → ผลลัพธ์ 8

ขั้นตอนการแก้ปัญหา

1. Pre-process: สร้างลิสต์ของ Cube ทั้งหมดที่มีค่า ≤ N โดยวน i จาก 1 ถึง ceil(N^(1/3)) คำนวณ i³ แปลงเป็นสตริงเก็บใน temp_cubes
2. Solve:
   • กลับลำดับ temp_cubes (เริ่มจาก Cube ใหญ่สุด)
   • สำหรับแต่ละ Cube ในลิสต์ ตรวจสอบว่าเป็น subsequence ของสตริง N หรือไม่ (คือสามารถลบหลักบางหลักได้แล้วเหลือ Cube นั้น)
   • ถ้าเจอ Cube แรกที่เป็น subsequence ให้คืนค่านั้นทันที (เพราะเรียงจากมากไปน้อย)
3. ถ้าไม่พบเลย คืน "Not Possible"

โค้ดตัวอย่าง Python

import math

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

def solve(num, temp_cubes):
    temp_cubes = temp_cubes[::-1]  # ใหญ่ไปน้อย
    for cube_str in temp_cubes:
        idx = 0
        for ch in num:
            if ch == cube_str[idx]:
                idx += 1
                if idx == len(cube_str):
                    return cube_str
    return "Not Possible"

def getLargestCube(n):
    cubes = preProcess(n)
    return solve(str(n), cubes)

print(getLargestCube(806))  # 8

อินพุต / เอาต์พุต

Input:  806
Output: 8