topcoder-like challenge

[Roy Lawson]

Most of the topcoder programmers don't program in VB
(topcoder.com), so I found a topcoder-like question (not
from their site as they copyright theirs) for anyone to
tackle. I don't think this one shouldn't be too
difficult...looks real easy.

Hopefully either more VB programmers join topcoder or
someone creates a competition just for .NET programmers
because it would be nice to have someone to compare my
code to Just keep track of your time...honor system
in full effect

Anyways, here is this one I found in a college website:


Programming Challenges: Factorial Parsing
The factorial, n!, of an integer is defined to be:

n! = ( n * ( n - 1 ) * ( n - 2 ) * ... * 2 * 1 )

An application of this formula is as follows, 5! = 5 * 4 *
3 * 2 * 1 = 120. This month's challenge is to find the
rightmost non-zero digit of n!. From the above example
this number is 2. The rightmost non-zero digit of 12! (
12! = 479001600 ) is 6.

Write a program that will input an integer between 1 and
14 inclusive and output the rightmost non-zero digit of
the factorial. For an added challenge, handle inputs
between 1 and 5000 inclusive.

Here are a few test cases for you to try:

Factorial Rightmost Non-Zero Digit
5 2
21 4
789 4
1000 2
4013 8

 

[CJ Taylor]

Hey Roy

Nice competition... how do you want the answer? =)

I can have it in 5 minutes probably. =)

-CJ

 

[CJ Taylor]

Haha! Tricky

because double can only support

1.79769313486231570E+308 or a 64bit number... in order to do 5000 you need
to do manual mathmatics and concatination to make it simple... =)

Nice challenge... But still, solveable in a few minutes. =)

-CJ

 

[Roy Lawson]

create this function within a class named Challenge:

Public Function Factoid(myFactorial As Integer) As Integer

Yeah, it shouldn't take too long. I am looking for a more
challenging one...will post my answer tonight.

-Roy

 

[Codemonkey]

Damn, the Decimal datatype only comes within 28 iterations of handling the
5000 :-S

I shall go sit in the corner with the Dunce Cap on.

 

[Codemonkey]

Ah, Boll*ks. On Second looks, it doesn't even do that.

Off to the stupid corner I go....

 

[CJ Taylor]

Yeah... I felt the same way... thats why I said you had to do the manual
mathmatics and string concatting... and THEN you can determine the right
most digit....

I may get bored and solve this tonihgt. =)

-CJ

 

[Roy Lawson]

I am so far unable to get the higher numbers to work (even
over 100) but the 1 to 14 inclusive is easy. There has
got to be some genious reading this who has an answer that
will get us to 5000

I don't see how concanting (or whatever we call it) the
numbers will work...you would still need to calculate a
very big number.

-Roy


Well, I did the easy part in about 16 minutes:


#################################################
Don't look below if you want to do the challenge#
#################################################


Public Class Challenge

Public Function Factoid(ByVal myFactorial As Integer)
As Integer
Dim x As Integer
Dim factorString As String
x = myFactorial - 1

While x >= 1
'multiply myfactorial by the next lower number
until x = 1
myFactorial = myFactorial * x
x = x - 1
End While
factorString = myFactorial
While factorString.Chars(factorString.Length - 1)
= "0"
factorString = factorString.TrimEnd("0", "")
End While
x = Val(factorString.Chars(factorString.Length -
1))
MsgBox(factorString)
Return x
End Function
End Class

 

[Fergus Cooney]

Hi Roy,

Another challenge.

This one was <hard>. I knew it would be an overflow problem but my first
whittle the bits method failed dismally!! :-(
The second worked but it's not proven - it's definititely a workaround.

The best method is a complete cheat. The first line is
Imports MathsLib.HugeNumbers

Regards,
Fergus

<code>
'Started 3:05
'Groan - Totally scrapped [actually I did keep Dim T As Decimal]
'Restarted with new method 3:37
'Finished 4:12
'
Public Shared Sub FactorialDigit (N As Integer)
Dim S As String
Dim C As String
Dim J As Integer
Dim I As Integer
Dim T As Decimal = 1

For I = 1 To N
'Do next multiplication
T = T * I
S = T.ToString

'Find last non-zero digit.
For J = S.Length -1 To 0 Step -1
C = S.Chars (J)
If C <> "0" Then
Exit For
End If
Next

'Remove zeroes.
S = S.Substring (0, J + 1)

'Remove top-end digits to keep within Decimal
If S.Length > 20 Then
S = S.Substring (S.Length - 20)
End If

'New value.
T = Decimal.Parse (S)
Next

Console.WriteLine ("N = {0}, C = {1}", N, C)

End Sub
</code>

 

[Roy Lawson]

"Imports MathsLib.HugeNumbers"

Aha, I didn't realize we had that library Cool! I am not opposed
to cheating


-Roy

 

[Roy Lawson]

Imports MathsLib.HugeNumbers

Sweet, I am not opposed to that Now where can we find this library?

-Roy

 

[Fergus Cooney]

Hi Roy,

Although it wasn't called MathsLib.HugeNumbers, I did see such a library
on my travels through one of the coders' sites. I just can't remember where or
enough to do a proper Google on it. (I've tried).

How did you get on with your own challenge ? What method did you use? Did
you simply throw away bits like I did or was your arithmetic legitimate
throughout?

And, , when do we get the next one.

Regards,
Fergus

 

[CJ Taylor]

LOL! Called on your sh*t!

=)

And then changes the subject. Very smooth Fergus. Very Smooth...

=)

String concatination will work as well, from a more visual perspective...
Basically, look at it this way.

imagine your in the 6th grade and you have to add 2 numbers. 2 VERY Large
numbers not able to be done on your brand new TI-30 eX.

So you write these 30 digit numbers out on a pieice of paper. 5 of em! Now
you know this big boy is going to be huge... in fact here is an example

132432235132512341234123412421
234123423423421341243234234231
123423423451235346457734598434
123423493823098348973429839483
234109123480865984390834928342

Now, you know that the calculator wont handle this... at least the TI-30.
So... we go old school mathmatics, what are we basically looking at here?
Character arrays? Yep... So, for the length of our array (also cycling down
the array of numbers... hmm 2 D array?) we just start adding down... first
column, 1 + 1+ 4+3+2

Doesn't make sense where these numbers come into play? Well, we know we can
get some rather large digits out of decimal or double right? Well, we just
figure out how many numbers we need to get...and add em up... which I
haven't quite figured out yet... but you can see how doing a manual
procedure might be easier to understand... I just dont feel like writing it
right now... =)

-CJ

 

[Nice Chap]

Heres my tuppence worth:

Private Function LastNonZeroDigitOfFactorial(ByVal nInput As Integer) As
Integer

Dim i As Integer = 1
Dim nPrev As Integer = 1

For i = 1 To nInput
' Get the Last Digit
If (nPrev * i) Mod 10 = 0 Then
nPrev = ((nPrev * i) / 10 ^ (Len(CStr(nPrev * i)) - 1)) Mod 10
Else
nPrev = (nPrev * i) Mod 10
End If
Next i

Return nPrev

End Function


This algorithm is based on the fact that only the last digit of every number
in the sequence decides the last digit of the final factorial value.

 

[Fergus Cooney]

Hi Nice Chap,

I don't know if you noticed the comments at the top of my method.

'Started 3:05
'Groan - Totally scrapped [actually I did keep Dim T As Decimal]
'Restarted with new method 3:37

The method that I started was the modulo-ten method that you have just
given. The Groan was when I found that it doesn't work.

I had written the use-Decimal-variables method so that I could have
some accurate values to work with at the lower end as Roy only gave us 5 and
21. The Decimal allowed a loop from 1 to 28.

Imagine my pleasure at scanning the results list and finding I was correct
with each value. Imagine, then, my horror at discovering that things went
wrong at 15 and then very wrong at higher numbers. Hear the Groan the came out
when I discovered why my method didn't work and I had to find another one!!

N = 1, LastDigit = 1, ModTen = 1
N = 2, LastDigit = 2, ModTen = 2
N = 3, LastDigit = 6, ModTen = 6
N = 4, LastDigit = 4, ModTen = 4
N = 5, LastDigit = 2, ModTen = 2
N = 6, LastDigit = 2, ModTen = 2
N = 7, LastDigit = 4, ModTen = 4
N = 8, LastDigit = 2, ModTen = 2
N = 9, LastDigit = 8, ModTen = 8
N = 10, LastDigit = 8, ModTen = 8
N = 11, LastDigit = 8, ModTen = 8
N = 12, LastDigit = 6, ModTen = 6
N = 13, LastDigit = 8, ModTen = 8
N = 14, LastDigit = 2, ModTen = 2
N = 15, LastDigit = 8, ModTen = 3 **
N = 16, LastDigit = 8, ModTen = 8
N = 17, LastDigit = 6, ModTen = 6
N = 18, LastDigit = 8, ModTen = 8
N = 19, LastDigit = 2, ModTen = 2
N = 20, LastDigit = 4, ModTen = 4
N = 21, LastDigit = 4, ModTen = 4
N = 22, LastDigit = 8, ModTen = 8
N = 23, LastDigit = 4, ModTen = 4
N = 24, LastDigit = 6, ModTen = 6
N = 25, LastDigit = 4, ModTen = 2 **
N = 26, LastDigit = 4, ModTen = 2 **
N = 27, LastDigit = 8, ModTen = 4 **
N = 28, LastDigit = 4, ModTen = 2 **

N = 5, LastDigit = 2, ModTen = 2
N = 21, LastDigit = 4, ModTen = 4
N = 789, LastDigit = 4, ModTen = 2 **
N = 1000, LastDigit = 2, ModTen = 8 **
N = 4013, LastDigit = 8, ModTen = 8
N = 5000, LastDigit = 2, ModTen = 4 **

When you multiply by a number, it usually only matters about the last
digit, for example, 15 * 127 is 1905 and 15 * 7 is 105 - both end with a 5.

However, when the digit multiplies to a multiple of 10, the addition
factor of the next digit comes into play, for example, 15 * 16 is 240 (150 +
90) but 15 * 6 is just the 90.

Condolences NC :-(

Regards,
Fergus

 

[Cian]

Hi Nice Chap,

I don't know if you noticed the comments at the top of my method.

'Started 3:05
'Groan - Totally scrapped [actually I did keep Dim T As Decimal]
'Restarted with new method 3:37

The method that I started was the modulo-ten method that you have just
given. The Groan was when I found that it doesn't work.
[snip]
When you multiply by a number, it usually only matters about the last
digit, for example, 15 * 127 is 1905 and 15 * 7 is 105 - both end with a 5.

However, when the digit multiplies to a multiple of 10, the addition
factor of the next digit comes into play, for example, 15 * 16 is 240 (150 +
90) but 15 * 6 is just the 90.

so just keep more digits (somewhere in the 100000s) when
you multiply by the 1000s you'll have three zeros to loose:

[pseudo code on]
int i=5005;
int y=1;
int fact = 1;

while (y less than i)
{
fact = fact * y;
y = y + 1;

'loose (all) trailing zeros...
while (fact mod 10 = 0)
fact=fact / 10;

'loose most significant digits...
if (fact / 100000 > 1)
fact = fact mod 100000;
}
[pseudo code off]

output:
....
4999 65266944 4
5000 334720000 2
5001 167393472 2
5002 467546944 4
5003 234860832 2
5004 304403328 8
....
Cian

 

[Howard]

I am in the process of switching from Delphi to VB.NET (in evaluation
phase).
This is how I would solve in Delphi (using recursion), would anyone
please show me the equivelent code in VB?

function TForm1.fact(n: Integer): Integer;
begin
if n<>1 then
Result:=fact(n-1) * n
else
Result:=1;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
factString: string;
i,numberToFact: Integer;
begin
factString:=IntToStr(fact(numberToFact));
i:=Length(factString);
for i:=Length(factString) downto 1 do begin
if factString <> '0' then begin
ShowMessage(factString);
Break;
end;
end;
end;

 

[Fergus Cooney]

Hi Cian,

Yes, the lose-the-top-end-bits method is what I ended up with, except that
I used strings rather than arithmetic. Did you record your time-to-results ?
We are recreating the atmosphere of the topcoder challenge whereby speed (of
coding not execution) and accuracy are the twin aims.

|| output:
|| ...
|| 4999 65266944 4
|| 5000 334720000 2
|| 5001 167393472 2
|| 5002 467546944 4
|| 5003 234860832 2
|| 5004 304403328 8

I'm very impressed by the output. None of the pseudo-code that I've <ever>
written has produced output - and without any print statements too, lol. Now
<that's> IntelliSense!! ;-)

Regards,
Fergus

 

[derian]

this is my pretty VB code... you will need to create a form with a button
and a text box.

notice there is no error checking so the code will barf if you enter a
non-integer... this is just the basic implementation

I also realize this thread is about 2 days old but i was on vacation and i'm
now throwing in my 2 cents!

\\\
private miTotal as double

private sub CalculateFactorial(byval sender as object, byval e as eventargs)
handles button1.click

miTotal = 1

if textbox1.text = 0 then
return 0
end if

if textbox1.text = 1 then
return miTotal
else
miTotal *= aiValue
CalculateFactorial(textbox1.text-1) 'Ahh, the art of
recursing
end if
end sub

private sub FindRightMostNonZero()
dim i as integer
dim lsTotalValue as string = miTotal.tostring()

for i = lsTotalValue.Length-1 to 0 step -1
if lsTotalValue.chars(i) <> "0" then
messagebox.show("The right most non-zero number is: " &
lsTotalValue.chars(i))
exit sub
end if
next
end sub
///
:\\derian

 

[Fergus Cooney]

Hi Howard, Derian,

The entry-level challenge is just finding solutions for numbers up to 14.

The <Challenge> is not to find factorials, nor is it just to find the
rightmost digit. - it's to find the rightmost digit of factorials up to 5000!

Are you game? ;-)

Regards,
Fergus