diff options
| author | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2020-02-29 23:16:06 +0000 |
|---|---|---|
| committer | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2020-02-29 23:16:06 +0000 |
| commit | 08bae3656260a757575a64c7bfebc5e71e1ed9af (patch) | |
| tree | daf82d754d0791251835eec10f68cb43f96b488a /challenge-049 | |
| parent | 9d6b0911692d12b7b9b583ffbca81c7c1cb0a4f1 (diff) | |
| download | perlweeklychallenge-club-08bae3656260a757575a64c7bfebc5e71e1ed9af.tar.gz perlweeklychallenge-club-08bae3656260a757575a64c7bfebc5e71e1ed9af.tar.bz2 perlweeklychallenge-club-08bae3656260a757575a64c7bfebc5e71e1ed9af.zip | |
- Added solution by Cheok-Yin Fung.
Diffstat (limited to 'challenge-049')
| -rw-r--r-- | challenge-049/cheok-yin-fung/perl/ch-1.pl | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/challenge-049/cheok-yin-fung/perl/ch-1.pl b/challenge-049/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..a1c7ee23fe --- /dev/null +++ b/challenge-049/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,52 @@ +#!/usr/bin/perl
+use strict;
+# use Math::BigInt; could be for fun
+
+sub max {
+ $_[0]>$_[1] ? $_[0] : $_[1];
+}
+
+my $N = $ARGV[0];
+my $C = $N;
+my $s = 0;
+my $t = 0;
+
+while ( $C % 2 == 0) {
+ $C /= 2; $s++;
+}
+
+while ( $C % 5 == 0) {
+ $C /= 5; $t++;
+}
+
+# N = 2^s * 5^t * C
+# Result = 2^max(s,t) * 5^max(s,t) * C * something
+
+
+my @D = (1);
+my $k = ( ($C==1) ? -1 : 0);
+my @key = ();
+
+while ($k != -1 and @key == () ) {
+
+ my $temp;
+ $temp = (10*$D[2**($k-1)]) % $C; # in simpler but slower terms, $temp = (10**$k) % $C;
+ $D[2**($k)] = $temp;
+ $k++;
+ if ($k != 0 or $k != 1) {for ( 1 .. 2**($k-1)-1 ) {
+ $D[2**($k-1) + $_] = ( $D[$_] + $temp) % $C ;
+ if ($D[2**($k-1) + $_] == 0) {
+ push @key, 2**($k-1) + $_;
+ # We cannot simply write: $key = 2**($k-1) + $_;
+ # because there could be more than one mulitples in 100...000 to 111..111, e.g. C=27;
+ }
+ }
+ }
+
+
+}
+
+@key = sort {$a <=> $b} @key;
+
+if ($C != 1) {printf "%0b", $key[0];} else {print 1;}
+print "0" x max($s,$t);
|