Đề bài
Viết một phép nhân a × b = c và gom tất cả chữ số của a, b và c lại. Phép nhân được gọi là n-pandigital khi các chữ số đó đúng là 1, 2, ..., n, mỗi chữ số dùng đúng một lần (không có số 0). Với n = 4, phép nhân 3 × 4 = 12 thỏa mãn. Hãy tìm mọi tích c xuất hiện trong ít nhất một phép nhân n-pandigital.
Hãy viết pandigital_products(n).
Đầu vào
n: Chữ số lớn nhất được dùng.
Đầu ra
Trả về tổng các tích c phân biệt. Một tích đạt được từ nhiều phép nhân chỉ được cộng một lần. Nếu không có tích nào, trả về 0.
Ràng buộc
1 ≤ n ≤ 9
Ví dụ
Đầu vào:
n = 4
Kết quả mong đợi:
expected = 12
Đầu vào:
long long n = 4;
Kết quả mong đợi:
long long expected = 12;
Đầu vào:
long n = 4;
Kết quả mong đợi:
long expected = 12;
Giải thích
3 × 4 = 12 dùng 1, 2, 3, 4 mỗi chữ số một lần và đó là phép nhân duy nhất như vậy, nên đáp án là 12.
Đầu vào:
n = 3
Kết quả mong đợi:
expected = 0
Đầu vào:
long long n = 3;
Kết quả mong đợi:
long long expected = 0;
Đầu vào:
long n = 3;
Kết quả mong đợi:
long expected = 0;
Giải thích
Với các chữ số 1, 2, 3, cách chia duy nhất có dạng 1 × 2 = 3, mà điều này sai, nên đáp án là 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Mọi phép nhân n-pandigital đều là một cách xếp các chữ số từ 1 đến n rồi cắt thành ba phần.
Gợi ý 2
Thử mọi cặp điểm cắt và kiểm tra xem tích hai phần đầu có bằng phần thứ ba không.
Gợi ý 3
Lưu các tích vào một tập hợp để mỗi tích chỉ được cộng một lần.
Độ phức tạp mong đợi
thời gian O(n! × n²), bộ nhớ phụ O(number of products)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.