programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Problem: Digit Products

Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:But I meant calculating permutations...

Ah, gotcha. Personally, I think I'd just use BIs and then report the way I was told to. Saves a lot of faffing around.

However, I was interested in that 'modulo (10^9 + 7)', and wondered if it might be a clue to the solution. Otherwise, why 10^9 + 7?

Well, I hope I have time to implement what I wrote about, since from tomorrow I'll be on holidays for a week, without internet

Have a great time either way,

Winston

Saloon Keeper
Posts: 15630
366
• 1
• Number of slices to send:
Optional 'thank-you' note:
1000000007 is a prime, which makes calculating the final result much easier if you already know certain properties about your answer. It's to avoid that calculating the modulus will be a time consuming step in your solution. Why use a modulo at all? Because typing in more than 10 digits in an answer form can be really annoying.

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:1000000007 is a prime, which makes calculating the final result much easier if you already know certain properties about your answer.

Ah. Thanks Stephan. Still getting to grips with modular arithmetic (not least because I find the notation a bit odd); but even so, I should have thought about the possibility of a prime.

Winston

Bartender
Posts: 5478
212
• Number of slices to send:
Optional 'thank-you' note:
Well, after a nice vacation with better weather than expected (but worse than hoped for) I implemented what I wrote before. However, it was trickier than I thought, and the code is also much longer than expected. But I did not write for brevity, but for ease of coding.

To illustrate the method, Lets say A = 50, B = 135, T = 12.

First T is transformed into a List of IntLists (= ArrayList<Integer>, but saves a lot of typing), and [2, 6] is one of these IntLists. This IntList is converted into a Frequencty table ('FT'), (a HashMap<Integer, Integer>, but again saves much typing).

So, for this case we have A, B and FT. What happens next depends very much on the length of these components. For A and B, this is simply the number of digits, and for FT, this is the sum of the values in the Map. An enum ('AandBandT') then characterizes the situation. In the case of the given values for A, B and FT it is CASE2: |A| = |FT| < |B|.

In the method 'permutationsCASE2' it is first calculated how many permutations of 'FT' are at least equal to A. Then, for lengths |A|+1 up to and including |B|-1, ones are added to FT'and all permutations are calculated. Finally, enough ones are added to FT to make its length equal to |B|, and the number of permutations are calculated that are at most B.

Well, that's it in essence. Special tricks were necessary when |A| = |B|, where only those permutations of FT must be calculated that are between A and B (inclusive).

Do not let the length of the code scare you off. It is Java7 code, I could have seriously shortened the code, but at the expense of making a complicated program even harder to read.
And is it all correct? I've done some testing for small values for A, B and T, and that was fine (well, after quite some repairing, that is).

Two questions remain: does anyone have a better (and hopefully shorter) solution? And is there a volunteer who wants to write a brute force method to test some bigger values for A, B and T?

Finally, I don't think there is much interest in this stuff. But if anyone has some questions or spotted some bugs, send them in.
Here's the code. All I can say to the author of this problem: you have probably a much more elegant solution, so I don't think I am spoiling this problem (I hope).

edit: there is a big bug in the 'productOfFactorials', but its repair is trivial and left to the reader.

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Well, after a nice vacation with better weather than expected (but worse than hoped for) I implemented what I wrote before. However, it was trickier than I thought, and the code is also much longer than expected. But I did not write for brevity, but for ease of coding.

Either way, it's very impressive. I've been away from this thread for a while, so it'll probably take me a day or two to get back into the "groove", but have a cow for effort in the meantime.

Winston

Ranch Hand
Posts: 40
1
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris
Bartender
Posts: 5478
212
• Number of slices to send:
Optional 'thank-you' note:
hi Tak Ming Laio,

thank you for this program! I did some checks, and with A = 50, B = 100.000.000 and K = 128, both programs agreed on 4.257. So, I guess it is fine.

You earned a cow, but unfortunately I have no clue how to give one. So, patience!

Stephan van Hulst
Saloon Keeper
Posts: 15630
366
• Number of slices to send:
Optional 'thank-you' note:
I gave him a cow for you, Piet.

Piet Souris
Bartender
Posts: 5478
212
• Number of slices to send:
Optional 'thank-you' note:
Thank you, Stephan.

Tak Ming Laio
Ranch Hand
Posts: 40
1
• Number of slices to send:
Optional 'thank-you' note:
Thank you Stephan and Piet, but for very large interval [A,B], this is not a fast solution. I will try another solution when have time.

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.