How to generate n number of ones in java?
I am stuck with an algorithm where I need to generate n number of digits '1', where n<=10^16
and n>=1
. I have successfully generated n number of units in for loop
with BigInteger
, because as long
well as string
failed to save this. But the problem is that this is a time limit 4 sec
and n>10^5
it takes more than 4 sec
. This is clearly generated in O(n)
. I think no relevant code is needed. I find many sites but cannot find a solution. Any better algorithm would be helpful. Thank you.
EDIT: This is a puzzle that introduces n
and m
and I need to print 111...(n times) mod m
where the limits are 1≤N≤10^16
and 2≤M≤10^9
. For example,
Suppose n=3
and m=3
, then print 111%3
which is0
Suppose n=5
and m=18
, then print 11111%18
which is 5
.
If you use long
or string
, then it gets called NumberFormatException
, then I change it to BigInteger
, then there is no exception.
public static void main(String[] ar){
Scanner in= new Scanner(System.in);
int t=in.nextInt();
while(t-->0){
BigInteger n=new BigInteger(Long.toString(in.nextLong()));
BigInteger m=new BigInteger(Long.toString(in.nextLong()));
BigInteger s=new BigInteger("1");
for(long i=1;i<n.intValue();i++)
s = s.multiply(new BigInteger("10")).add(new BigInteger("1"));
System.out.println(s.mod(m));
}
source to share
If S (n) - n units, then these equations take place:
S(1) = 1 S(2n) = S(n) * (10^n + 1) S(n+1) = S(n) * 10 + 1
You can use these two recurrent expressions (modulo m) to calculate S (n) modulo m.
S(n) % m =
1 [if n is 1]
((S(n/2) % m) * ((10^{n/2} % m) + 1)) % m [if n is even]
((S(n-1) % m)) * 10 + 1) % m [if n is odd]
You should still be able to calculate 10 ^ n% m efficiently, and while this can be done using exponentiation, you can also use the fact that 10 ^ n = 9 * S (n) +1.
Using this last relation between 10 ^ n and S (n), we arrive at this system of equations, which is easily coded as a recursive (or iterative) program:
S(n) % m =
1 [if n is 1]
x*(9x+2) % m where x = S(n/2)%m [if n is even]
((S(n-1) % m) * 10 + 1) % m [if n is odd]
In Python this gives runtime for n = 10 ^ 16, m = 10 ^ 9 out of 0.017s on my laptop, which is within 4 time frames.
source to share
I have an idea that might help you optimize your code in some way.
Below is my direct translation of my math notes (with comments in italics), so if you find anything confusing please indicate it.
How to find if a number is divisible by 37 (in your case it is m)
We have the following
10 ^ 0 ≡ 1 (mod 37)
10 ^ 1 ≡ 10 (mod 37)
10 ^ 2 ≡ 26 (mod 37)
10 ^ 3 ≡ 1 (mod 37)
basically do this until you see repetition
So, if we want to see if the number is divisible by 37 (or what's left), we plug in the powers of 10 with the coefficients we got above. This means that a * 10 ^ 3 + b * 10 ^ 2 + c * 10 ^ 1 + d mod 37 = a * 1 + b * 26 + c * 10 + d mod 37.
Real number example
(number with 10 ^ 16 digits 1
) mod 37 = (1 + 26 + 10 + 1) * 10 ^ 16/4 mod 37 = 21
you can repeat this process more than once, each time you do it, the resulting number decreases proportionally (a number with 10 ^ 16 digits is reduced to a number with 16 digits)
source to share