I should have noted that this can handle inputs up to about 2^32 / (10 * x). Run time is proportional to the number of 1's. You can also add a bit of code to discover the digits of the multiplicand.
I was able to verify with lisp bignums that: 25,514 1's is equal to 76543 * ( a 25,509 digit number ) An unverified one because my machine ran out of memory while multiplying (but which took about .05 seconds to find) is: 1,638,726 1's = 9,876,543 times (a 1,638,719 digit number ) On Oct 12, 4:35 pm, Gene <[email protected]> wrote: > First note: > > 0 * 3 = 0 > 7 * 3 = 21 > 4 * 3 = 12 > 1 * 3 = 3 > 8 * 3 = 24 > 5 * 3 = 15 > 2 * 3 = 6 > 9 * 3 = 27 > 6 * 3 = 18 > 3 * 3 = 9 > > Important is that the final digits of each line count 0 to 9. > > Now you can build an answer right to left. > > Example: 123. > > Check the table to get the rightmost 1. > 7 * 123 = 861 > > Now you need to add ...50 to make the 10's digit a 1. So > > 50 * 123 = 6150 + 861 = 7011 > > And now add 100 to get the third 1... > 700 * 123 = 86,100 + 7011 = 93,111 > > Following this pattern: > 6000 * 123 = 738,000 + 93,111 = 831,111 > 60000 * 123 = 7,380,000 + 831,111 = 8,211,111 > 300000 * 123 = 36,900,000 + 8,211,111 = 45,111,111 > > Okay. That's enough. We stop when the carry digits finally turn out > to be all 1's. > > In a program once we've arranged for a rightmost 1 we can shift it out > of the calculation by dividing everything by 10. At the same time we > can shift out the trailing zeros in the multiplicands. > > So here's a quick implementation. Sorry in advance for mistakes, but > it seems to be working okay: > > #include <stdio.h> > > // If x is all 1's (including zero of them), return > // how many there are. Otherwise return ~0u. > unsigned all_ones(unsigned x) > { > unsigned n = 0; > while (x) { > if (x % 10 != 1) > return ~0u; > x /= 10; > ++n; > } > return n; > > } > > // A table s.t. (x + 3 * mul[x % 10]) ends in 1. > unsigned mul[] = {7,0,3,6,9,2,5,8,1,4}; > > // Return n s.t. x divides sum_{i=0 to n-1} 10^i . > // x must be congruent to 3 mod 10. > unsigned ones(unsigned x) > { > unsigned n, carry = x; > for (n = 0; all_ones(carry) == ~0u; n++) { > carry = (carry + mul[carry % 10] * x) / 10; > // printf("%d\n", carry); > } > return n + all_ones(carry); > > } > > int main(void) > { > unsigned x; > if (scanf("%u", &x) == 1 && x % 10 == 3) > printf("%u divides %u 1's\n", x, ones(x)); > return 0; > > } > > On Oct 10, 9:20 am, VIHARRI <[email protected]> wrote: > > > > > > > > > For every number that has 3 in its units place has one multiple which > > has all one's i.e. 111 is > > such multiple and 13 has a multiple 111111. Write a program to find > > such multiple for any > > number that has 3 at its units place. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
