How to use BigInteger in java? - Codechef

Sharing buttons:

hey guys is gkcs,

today, we'll be talking about BigIntegers and

It's a pretty interesting class in Java

I have seen people from other you know people using other programming languages come in to Java because of this particular class

In competitive programming there are questions in which you have these huge

Numbers, and you need to perform operations like multiplication addition and stuff like that. You know on them and

One of the simple ways to implement. This is

Provided in Java through begin teachers, so what we are going to do is going to discuss

How we can construct big integers, how we can

perform operations on them and also we are going to be solving a code chef question using big integers and

Try and get an Ac for that

So firstly let's let's try and construct a big integer. So these objects are

Rather easy to construct in the constructor. You can pass in a string which contains your

Integer value, and that's what you have

another way to do this is

if you know you have a

number which is [not] too big

Then you can simply pass in the value

As a long so if it falls within the first 64 bits, I mean within 64 bits

then you can pass this in

Another way to do. This is if you have

The simplest number so of course this isn't a new way to do it. It's just that some constants like 0 1 2

There they already provided by a big integer so 2 is in provided actually it's 10

Now let's come to the basic operations of [B'keen] teacher

You can multiply a big integer with another big integer using the multiply operation

Now what happens is if you try to print this number big integer

then that will bring the object and keep things simple let's bring this value down to

let's say 55, so

22 into 55 is 1 2 1 0

so we are expecting 1 2 1 0

Let's see if we get that

Ok we got a value of 22

Why did that happen we just multiplied this big integer with 55 and still [more] 22?

The reason for this is as [it's] suggested by intelligent

Is that big integer or multiply is ignored the result of big integers or multiplies ignored now?

What we need to understand is that big integers are immutable classes?

When I say that a class an object is immutable it means that its internal state can never be [changed]

if this big integer has a value of 22, whatever operations you perform on it its value that it will never change, [so]

[when] I say x 55 what's actually happening is a new object is being created in

Which 2020 55 is being computed and inserted?


Any kind of operations you can you can then you know add to this integer?

It's a 13 you can then divide it

Because you need to add a big integer to this

so value 13 if you if you can feel like dividing it by

value of 12

Everything is fine, but the important thing is [that] again intelligent suggesting

It's ignored because you actually haven't stored the result this class is this object is not being affected at all

So what we need to do is we actually need to take the result divide and let's name these things a little more cleanly

Be and [you'll] see and then we have a result

now if we print the result

We should get what we want. We should get one two one zero

In fact we are going to get 1 2 1 0 [+] 13

1 2

3 divided by 12 so 101 should be the answer. That's what we are getting

So [again], [we're] getting [here]

So these are the kind of operations you can perform and big integer a few interesting things

Excuse me are that you can you can do more operations on beginning each

So this does exactly what C mod k would do if you had a new begin teacher


That's that's these two operations are equivalent. Except that you can do these on really big numbers using using this class

The second interesting thing is [that] you can you can do mod inverse

Which means you take this number and find the model inverse with a long number

This is particularly useful in

Programming contests because often we are asked to find mod inverse and I still do not know the algar to find out a modern was

between teacher saves me every time

The final thing that we need to look at before we jump into the problem is

What does big integer offer?

In it since multiplication operation


When we go out and multiply?

Usually it's an N square operation the high school math that we did

we took each digit and multiplied the other number by it and then you know append zeros as we go ahead in the in the

digit line each

What begin teacher does [is] slightly smarter it does the same thing?

up to a particular threshold and then it starts using these interesting algos, so

at best big integer

Can change your n square? I'll go to N. List of our one point four six five

So there's a lot of documentation explaining when and why this is used and you can go through it

But the interesting thing is begin teachers are pretty efficient in multiplications


If you are looking for extremely efficient multiplication then fast fourier transform is the only way forward

But otherwise these these operations are pretty efficient by themselves

okay, and

One final thing is that big integers can also tell you whether the number is a probable prime

If you look at the kind of parameters that it needs it needs a bit length and a random object

So what it [says] is that it it returns a positive big integer?

That is probably prime with the specified bit length the [probabilities] [are] [the] integer return is it?

So you can go through this, but what it's actually doing is


Numbers which are probably prime?

by taking a

You can say random function and then also the size of the of the number

But not a random function or a random object. It uses this to actually create the

the number

Similar to that is big integer is probable trying

In which you can pass in certainty

Certainty is this is Parameter which?

as it increases your

The probability that the number is prime is exponentially increasing

So is probable prime tells you if the number is probably prime and the error rate reduces exponentially as you increase?

This value certainty and again as usual. We can read about the documentation over here

Right so I think we are ready now to jump into the code chef problem. Which is

Fn control or something

essentially what it asks is

Make factorials or numbers and print them out so that's exactly what we are going to be doing we are going to be

using this function I

would begin teacher

[to] [you] in which what you do is you you pass in this integer n, and you get n. Factorial?

So let's just mention that [the] turns you [have] this cool thing

Right so how do we do this we take this?

big integer which will store our result and we initialize it to value of 1

now what we do is we set result to

2 N factorial and in the inner loop what we are doing is

We are going on setting result to the multiplication of the next number with this result

Again very important to know is that this is not correct

This is correct you're [assigning] result to the new object which is being created

And finally we can just return the sun

In our main program what we need is is we need a you know input reader

bufferedreader [dot] [readline] should

Should give us our input, and then all we need [to] do is actually

Forgot to make it static

So all we need to do is pass in this number

to the

Thing that we need and let's just test this once

Let's pass in five

We have 24 now that's an issue. That's [because] I have a bug here and now it should work, so

[it] was less than I'm so custom to always writing less than that. I now think of an equal to

120 is the result that is exactly what 5 factorial is

So what they're expecting is

Us to take a certain [number] of test cases along with n. So that that's fine. We just take the test cases over here

And then for each test case we are going to be taking in

[write] simple enough

ok we can we can actually pass this in directly so I just [inline] that [and]

yeah, we

We could in fact in 92, but that all right that's useless

So let's let's just go back [to] that

Sample input that they have let's try and see if our program does exactly what they're asking

for test cases

one to one [twenty] and six yes, it seems like we have the solution you can go ahead and write test cases, but

Let's submit this solution. Finally

Right I'll remove the package name also code chef has this weird thing [that] you need to name your class mean oh

God, right, I better copy this

Because I have to set my compiler to Java

Now that we are done with this let's try and submit this should work

If it doesn't then it's big integers fault

Come on

please work ah

Correct solution, so that's pretty much it for big integers if you have any special

Requirements or any comments or queries or suggestions anything just put them in the comments below?

I'll be I'll be you know looking at all them, and I'll be happy to help and best of luck. Thanks, Sierra