โจทย์
เขียนการคูณ a × b = c แล้วดูเลขโดดทั้งหมดใน a, b และ c รวมกัน สมการนี้จะเป็น n-pandigital เมื่อเลขโดดเหล่านั้นคือ 1, 2, ..., n โดยแต่ละตัวใช้เพียงครั้งเดียวพอดี (ไม่มีเลขศูนย์) เช่น สำหรับ n = 4 สมการ 3 × 4 = 12 เข้าเงื่อนไข ให้หาผลคูณ c ทุกค่าที่ปรากฏในสมการ n-pandigital อย่างน้อยหนึ่งสมการ
จงเขียนฟังก์ชัน pandigital_products(n)
อินพุต
n: เลขโดดที่มากที่สุดที่ใช้
เอาต์พุต
คืนค่าผลรวมของผลคูณ c ที่ไม่ซ้ำกัน ผลคูณที่ได้จากหลายสมการให้บวกเพียงครั้งเดียว ถ้าไม่มีเลยให้คืนค่า 0
เงื่อนไข
1 ≤ n ≤ 9
ตัวอย่าง
อินพุต:
n = 4
ผลลัพธ์ที่คาดหวัง:
expected = 12
อินพุต:
long long n = 4;
ผลลัพธ์ที่คาดหวัง:
long long expected = 12;
อินพุต:
long n = 4;
ผลลัพธ์ที่คาดหวัง:
long expected = 12;
คำอธิบาย
3 × 4 = 12 ใช้ 1, 2, 3, 4 ตัวละหนึ่งครั้ง และเป็นสมการเดียวที่เข้าเงื่อนไข คำตอบจึงเป็น 12
อินพุต:
n = 3
ผลลัพธ์ที่คาดหวัง:
expected = 0
อินพุต:
long long n = 3;
ผลลัพธ์ที่คาดหวัง:
long long expected = 0;
อินพุต:
long n = 3;
ผลลัพธ์ที่คาดหวัง:
long expected = 0;
คำอธิบาย
เมื่อใช้เลขโดด 1, 2, 3 การแบ่งที่ทำได้มีแค่แบบ 1 × 2 = 3 ซึ่งไม่เป็นจริง คำตอบจึงเป็น 0
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
สมการ n-pandigital ทุกสมการคือการเรียงเลขโดด 1 ถึง n แบบหนึ่งที่ถูกตัดออกเป็นสามท่อน
คำใบ้ 2
ลองคู่จุดตัดทุกคู่ แล้วตรวจว่าสองท่อนแรกคูณกันได้ท่อนที่สามหรือไม่
คำใบ้ 3
เก็บผลคูณไว้ในเซต เพื่อให้แต่ละค่าถูกบวกเพียงครั้งเดียว
ความซับซ้อนที่คาดหวัง
เวลา O(n! × n²), หน่วยความจำเพิ่ม O(number of products)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน