ตรวจสอบว่าตัวเลขย่อยทุกตัวมีผลคูณหลักต่างกันหรือไม่ใน Python

ภาพรวม

บทความนี้ตรวจสอบว่า "ตัวเลขย่อย" (sub-numbers) ทุกตัวของเลข n มี "ผลคูณหลัก" (digit product) ที่ไม่ซ้ำกันหรือไม่ ตัวเลขย่อยคือเลขที่สร้างจากหลักติดกันของเลขต้นฉบับ

ตัวอย่าง

เลข 135 มีตัวเลขย่อย: 1, 3, 5, 13, 35, 135
ผลคูณหลัก: 1, 3, 5, 3, 15, 15 → มีซ้ำ (3 และ 15) → คืนค่า False

เลข 235 มีตัวเลขย่อย: 2, 3, 5, 23, 35, 235
ผลคูณหลัก: 2, 3, 5, 6, 15, 30 → ทั้งหมดไม่ซ้ำ → คืนค่า True

อัลกอริทึม

1. แปลงเลขเป็นสตริง แล้วแยกเป็นลิสต์หลัก
2. ใช้ลูป巢套 สร้างทุก substring (i ถึง j)
3. คำนวณผลคูณหลักของแต่ละ substring
4. เก็บในเซต ถ้าซ้ำ คืนค่า False

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

def dig_prod(digits):
    product = 1
    for d in digits:
        product *= d
    return product

def solve(num):
    num_str = str(num)
    length = len(num_str)
    digits = [int(num_str[i]) for i in range(length)]
    prod_set = set()
    for i in range(length):
        for j in range(i, length):
            item = dig_prod(digits[i:j+1])
            if item in prod_set:
                return False
            prod_set.add(item)
    return True

n = 235
print(solve(n))  # True

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

จำนวนตัวเลขย่อยของเลข n หลัก คือ n(n+1)/2 อัลกอริทึมนี้เป็น O(n^2) เหมาะสำหรับเลขไม่มากหลัก (เช่น < 10 หลัก)