Julka — SPOJ

Read the question and scratch your skull for a while thinking about some math.

Maybe put a pen onto a paper nearby!?It shouldn’t take more than a few minutes to crack the logic.

Well, if math has never been your friend, don’t worry pal, we are in this together!So basically the question goes like this:Find two numbers A and B, whose sum and the difference is given to us as input.

Input: Sum (A + B)Diff (A — B)Let sum = S and diff = D;S = A + BD = A — BWe have 2 equations and 2 unknowns(A and B).

Let’s solve them.

A = (S + D)/2B = (S — A)That’s it.

Job done.

!Now, let’s code this.

 The headache is this big numbers that we need to handle.

What are these big numbers after all?Consider the ranges:int: -2¹⁵+1 to 2¹⁵+1 long: -2³¹+1 to 2³¹+1long long: -2⁶³+1 to 2⁶³+1The question deals with numbers of the range 10¹⁰⁰ (say whaaa!?).

And I see no data types above handling these BIG numbers.

In Java, a specific class called BigIntegers is used to handle such big numbers that can’t be handled by primitive data types such as the ones mentioned above.

 We will handle these numbers in C++ and learn to add, subtract and divide without using any pre-defined classes like BigInteger.

The idea, basically…Treat these numbers as vector of integers with each index storing a digit.

So the number 567824 instead of being stored in a single int variable, will now be stored as a vector<int> num.

vector<int> storing the numberSo now, if the number is as big as 10¹⁰⁰, its like having a vector of size 100.

Wow, that was something!All we need to do now is to:[1] Add S and D and divide the sum of S and D by 2 to get num1.

[2] Subtract num1 from S to get num2.

The above steps involve an addition operation, a divide by 2 and a subtraction operation on vectors of integer types.

Let’s write functions that would do the aforementioned for us.

That seriously was a lot of code!Well, we are in the Endgame now.

 :PThat’s all folks! Go ahead, Submit.

! Happy Coding!! :).

. More details

Leave a Reply