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.
