search

stevenhalim / cpbook-code

CP4 Free Source Code Project (C++17, Java11, Python3 and OCaml)
2k stars 493 forks source link

Tip about the UVa 00725 - Division #113

Open marcoshass opened 1 month ago

marcoshass commented 1 month ago

Hi, I have cpbook 4th edition and I'm struggling to understand the UVa 00725 problem:

Ref UVa 00725
Find and display all pairs of 5-digit numbers that collectively
use the digits 0 through 9 once each, such that the first number divided by the second is
equal to an integer N, where 2 ≤ N ≤ 79. That is, abcde/fghij = N, where each letter
represents a different digit. The first digit of one of the numbers is allowed to be zero, e.g.,
for N = 62, we have 79546/01283 = 62; 94736/01528 = 62.

2nd paragraph on page 131 says:

"Quick analysis shows that fghij can only range from 01234 to 98765 which is at most ≈ 100K possibilities"

But I have no idea how this analysis was performed, could someone give a hint on how these 100K possibilities were obtained? something step by step would help .. Thks!

seffendy commented 1 month ago

It's just a rough approximation.

The number of possible values for fghij is the same as the number of ordered subsets of size 5 from a set with 10 elements -- this is what a permutation is.