CodeChef Hints: January long 2018

Rectangle: Given four integers abc and d, we have to determine if there’s a rectangle such that the lengths of its sides are abc and d (in any order) .

Solution: The easiest problem of this set. We just need to find 2 unique integer each having frequency 2. Or only a single integer having frequency 4, in case it is a square (also a rectangle).

Maximum Score: Given N integer sequences, each sequence having N integers, we need to find the maximum number we can get by taking only a single element from each sequence so that, element of i-th sequence is strictly greater than element of (i-1)-th sequence.

Solution: We will solve this in reverse order. First think, if we need to make out score maximum, we should always take the maximum number of the last sequence. After that we will take integer strictly less than that one from previous sequence. Say we have sequence:
1, 2, 10
9, 5, 12
2, 12, 8
We will take values from last sequence. First we took 12, maximum value of the last sequence. Then we come to previous sequence. We need to take value from this sequence which is strictly less than 12. Simple binary search using lower bound technique will give us the index of our desired value. If no such index is present then there is no solution. If you don’t know about lower bound, look here. Of course we need to sort every sequence for this too.

K-Concatenation: Given an array A of size N, we need to make K copies of the array using concatenation of the array values, and then find the maximum subarray sum of that final array.

Solution: As N and K is so big, we can’t simply concate  A by K times and then find the maximum subarray sum. So, what we can do? we can observe somethings.

First observation: If summation of every element of the array is positve, then the result is summation of all the elements * K

Second observation: If all elements are negative, then the answer is the greatest number of all the elements.

Third observation: If there are mixed elements, then we can find largest subarray sum in 1-D space using Kadane’s algorithm. Now for using Kadane, there is some observations too. If K == 1, we have simply array A, and with the help of Kadane, we can easily find largest subarray sum from there. Notice, if K > 2 what should we do? As we have mixed elements, no matter how large K is, only concatening 2 times is enough for us to find the largest sum. Ok, why 2 times? See a case A = 1 -2 1 and K = 4 suppose, then we get
1 -2 1 1 -2 1 1 -2 1 1 -2 1 ; if we use Kadane here, we will get 2 as our maximum sum.
1 -2 1 1 -2 1 ; if we use Kadane here, we will also get 2. As we are concatening, each time a new concatenation arises, it depends on the previous structure also. So by concatening 2 times, we will get what, by concatening K times, we will get same result.

Final observation: It is the most important of all. Notice these case:  
A = 1 1 -9 2 3 4, K =  3, so, we get:
B = 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4

Now, we will check first observation: total sum of A = 2, as K = 3 times, so we get = 6. We will store this value to storage1.

Now, for second observation, all elements are not negative, so we will store a big negative number like -9999999999999…. to storage2.

Third observation, as there are mixed elements, we will use Kadane’s algo to find maximum subarray sum for 1 1 -9 2 3 4 1 1 -9 2 3 4  . And that is 11. So, storage3 = 11.

But let’s see our final array : 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4; If we take this subarray, we get 13. So this is the final observation of this problem. We need to find two maximum values of our initial array A. We will call it forward_max and backward_max.
forward_max = 1 1 -9 2 3 4 = 9
backward_max = 1 1 -9 2 3 4 = 2
So, our storage4 will be = forward_max+ S*(k-2) + backward_max ; S = summation of array A = 2
As, we took forward_max of our first part, backward_max of our last part, we are left with K-2 parts between. so we need to take all the remaining K-2 parts sum. Also notice, for final observation, K should be > 2

Our final result will be maximum of all the four storages 🙂

Partition the numbers: Given N and X, we need to partition N numbers in such two sets, that both set will have equal sum after subtracting X from N elements(consider elements from 1 to N).

Solution: First we will calculate summation of N elements using series sum formula: N*(N+1)/2 . Now subtract X from this sum. So, sum = N*(N+1)/2 – X.
Now, if sum is odd then there is no solution, as we can’t make an odd number partitioned in two disjoint sets. Also if N <= 3, there is no solution.

Now, when sum is even, we will make sum/2 using our 1 to N numbers without X. We will iterate from N to 1, each time we will check if needed sum is getting zero or not. if we can subtract a value, we will do that, and mark that value as set 1. One important thing is to notice that, while subtracting an integer, we need to check if the remaining sum can be represented by other available integers or not. There is may approach to solve this problem. Implement it however you want keeping some corner case in mind.

String Merging: You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.

Solution: This is a simple dynamic programming problem. Greedy solution won’t help you there. What we need to do is simply find the longest_common_subsequence of String A and B. Then our result would be M + N – LCS(A,B). But first, finding LCS between A and B we need to modify A and B string in such a way that no same character right beside each other. If A = “aaaxyyyzza”, we need to modify it as “axyza”, as there is no same character right after one character. Then we will perform LCS operation in our modifued string and get the final result.

 

Advertisements

Calculate Summation of GCD(i,n); for i = 1 to n

আমাদের এবারের কাজ হল ১ থেকে n পর্যন্ত সবগুলো সংখ্যার সাথে n এর গ.সা.গু. বের করে তাদের যোগফল বের করা।
শুনতে ব্যাপারটি সহজ মনে হলেও, আসলে ঠিক সহজ না, যদি না আমরা সঠিক এপ্রোচ না জানি। নরমালি আমরা যখন প্রোগ্রামিং এ নতুন, তখন আমরা ১ থেকে n পর্যন্ত লুপ চালায়ে তাদের যোগফল বের করতাম।


এখন কথা হচ্ছে, এভাবে করলে আমরা বড় বড় সংখ্যার জন্য আমরা TLE খাবো। যেমন n = 1000000000 এর জন্য আমাদের প্রচুর সময় লাগবে, ( ইচ্ছে করলে উপরের কোডটি নিজ দায়িত্বে রান করে দেখে নিতে পারো :3 )

এখন তাহলে আমরা কিভাবে এর সমাধান করবো? খেয়াল করলে দেখবো যে, আমরা যখন ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যাগুলোর সাথে n এর গসাগু বের করার চেষ্টা করছি,তখন আসলে আমরা প্রতিবার n এর সবগুলো বিভাজক( all divisor ; there maybe multiple occurance of divisors) নিয়ে তাদের যোগফলটা নিচ্ছি। যেমনঃ  n = 8 হলে, gcd(1,8) + gcd(2,8) + gcd(3,8) + gcd(4,8) + gcd(5,8) + gcd(6,8) + gcd(7,8) + gcd(8,8)  = 1+2+1+4+1+2+1+8 = 20।
এখানে খেয়াল করে দেখি যে, আমরা কিন্তু ১,২,৪,৮ ছাড়া আর কিছু যোগ করছিনা! আর এই সংখ্যাগুলি কিন্তু আসলে ৮ এর বিভাজক (divisor)। আমরা আপাতত গোনায় বাদ রাখলাম কোন সংখ্যা কতবার নিচ্ছি, কিন্তু আসল কথা হচ্ছে আমরা n এর divosr গুলিকেই নিচ্ছি আমাদের ক্যাল্কুলেশন এর জন্য। তাহলে বুঝা যাচ্ছে আমাদের আসলে n এর divisor গুলি বের করতে হবে। আর আমরা O(√n) কমপ্লেক্সিটি তে n এর divisor বের করতে পারি। কাজেই, n = 1000000000 এর জন্য আমরা 31622.77.. কমপ্লেক্সিটিতে divisor গুলি বের করে, এরপরে আমাদের বাকি কাজ করবো।

তাহলে  n = 8 এর জন্য, আমাদের যোগফল অনেকটা এরকম হবে দেখতেঃ

\sum _{ i=1 }^{ 8 }{ gcd(i,n) } = coef1*(1)+coef2*(2)+coef3*(4)+coef4*(8)

এখানে coef1,coef2… এগুলোই আমাদের বের করতে হবে। divisor গুলি আমরা আগেই পেয়ে গেছি।
১ থেকে n পর্যন্ত সংখ্যাগুলোর সাথে n এর গ.সা.গু. বের করতে গেলে,গ.সা.গু = ১ কতবার আসবে, সেই সংখ্যাটা আসলে n এর অয়লার ফাংশন। অয়লার ফাংশন সম্পর্কে না জানলে এই লিঙ্ক দেখার অনুরোধ রইল আগে।
আচ্ছে এখান থেকে আমরা একটু মনযোগ দেয়ার চেষ্টা করি, 

phi (8) = 4.
phi (4) = 2.

phi (2) = 1.
phi (1) = 1.
আমরা এখানে আসলে ৮ এর divisor গুলির phi এর মান দেখলাম।
আচ্ছে এখন দেখা যাক, phi(8) = 4 এর জন্য, কোন কোন জোড়া নিলে আমাদের গসাগু ১ আসছেঃ
(1,8), (3,8), (5,8), (7,8); কাজেই, আমাদের coef1 = 4 হবে। ( coef1*(1); এই 1 এর মানে হচ্ছে, ঐসব জোড়া আমরা নিবো, যাদের মাঝের গ.সা.গু. = 1 হবে, এরকম জোড়া আছে 4 টি, কাজেই আমাদের coef1 = 4 )
এখন আমরা বের করবো coef2 এর মান। কাজেই আমাদের বের করতে হবে এমন কতটি জোড়া আছে, যারা 8 এর সাথে গ.সা.গু.  = 2 হবে। এজন্য আমাদের দরকার phi(8/2) = phi(4) এর মান। আমরা আগেই বের করে রেখেছি, phi(4) = 2. কাজেই আমাদের coef2 = 2. একইভাবে, coef3,coef4 বের করতে পারবো আমরা। ফাইনালি,

coef1 = phi(8/1) = phi(8) = 4. ; divide by first divisor = 1.
coef2 = phi(8/2) = phi(4) = 2. ; divide by second divisor = 2.
coef3 = phi(8/4) = phi(2) = 1. ; divide by third divisor = 4.
coef4 = phi(8/8) = phi(1) = 1. ; divide by forth divisor = 8.

কাজেই, আমাদের ফাইনাল রেজাল্ট ঃ
phi(8/1)*1 + phi(8/2)*2 + phi(8/4)*4 + phi(8/8)*8
= 4*1 + 2*2 + 1*4 + 1*8 = 20
 

অ্যালগরিদম (Algorithm)

without pre computing phi values:


এখন আমাদের অনেক কুয়েরি থাকলে আমাদের আগে থেকে phi এর মান বের করে রাখতে হবে। ঐ ব্যাপারটা তোমরা নিজেরা করে দেখো। আবার যদি আমাদের n এর মান অনেক বড় হয়ে যায় যে, আমরা O(√n) এও TLE খাচ্ছি, তাহলে আমাদের number theorem এর অন্যরকম এপ্রোচ নিতে হবে। এগুলো নিয়ে পরে আলোচনা করা যাবে। 

স্লাইডিং উইন্ডো (Sliding Window Technique)

প্রোগ্রামিং কন্টেস্টে আমাদের অনেক সময় ৩ বা ৪ বা এরচেয়েও বেশি লুপ এর কোড লিখতে হয়। ব্যাসিকালি ব্রুটফোর্স যাকে বলে। এখন আমরা যেই টেকনিক দেখবো, এটি এরকম একাধিক লুপ এর প্রব্লেমকে কম সময়ে সল্ভ করে দিতে পারবে। 

স্লাইডিং উইন্ডো সমস্যার বিভিন্ন রূপ আছে। কিন্তু তাদের সবারই একটি কমন বৈশিষ্ট আছে : একটি সাব-অ্যারেকে (আমরা একে ‘উইন্ডো’ বলে থাকি, যা স্ট্যাটিক বা ডাইনামিক দৈর্ঘ্য থাকতে পারে) আমরা  n সংখ্যক উপাদানগুলির অ্যারে এর বাম থেকে ডান দিকে লিনিয়ারভাবে সরায়ে কিছু কম্পিউট করার চেষ্টা করবো। এভাবে উইন্ডো স্লাইড করার টেকনিক কেই স্লাইডিং উইন্ডো বলে। স্লাইডিং উইন্ডোর অনেক রকম ভ্যারিয়েশন আছে। যেমন ঃ 

  1. একটি অ্যারের মাঝে ফিক্সড সাইজের কোন সাব-অ্যারের ম্যাক্সিমাম সামেশন বের করা। যেমন ঃ অ্যারে  A = {10, 40, 10, 30, 20} এবং উইন্ডো সাইজ w = 3 হলে, মাক্সিমাম সামেশন = 40+10+30 = 80. 
  2. একটি অ্যারের মাঝে ফিক্সড সাইজের সকল সাব-অ্যারের ম্যাক্সিমাম অথবা মিনিমাম সংখ্যা বের করা। যেমন ঃ
    অ্যারে A = {0, 5, 5, 3, 10, 0, 4} , n = 7 এবং উইন্ডো সাইজ w = 3, হলে এখানে n-w+1 = 5 টি ভিন্ন ভিন্ন সাব-অ্যারে আছে যাদের সাইজ = 3; {0, 5, 5}, {5, 5, 3}, {5, 3, 10}, {3, 10, 0}, {10, 0, 4}. এবং আমরা এদের ম্যাক্সিমাম সংখ্যা বের করতে চাইলে এগুলি হবে ঃ 5, 5, 10, 10, 10 প্রতি সাব-অ্যারের জন্যে। 
  3. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর, যার এলেমেন্ট এর সাম, নির্দিষ্ট কোন সাম থেকে বড়/ সমান/ ছোট হয়। যেমন ঃ অ্যারে A = {5, 1, 2, 3, 4, 2} এবং S = 7 হলে,
    মিনিমাম দৈর্ঘ্য == 7 : 2,  {5, 1, 2, 3, 4, 2}
    মিনিমাম দৈর্ঘ্য > 7 : 3,  {5, 1, 2, 3, 4, 2} , {5, 1, 2, 3, 4, 2}, {5, 1, 2, 3, 4, 2}
    মিনিমাম দৈর্ঘ্য < 7 : 1,  {5, 1, 2, 3, 4, 2} ; যেকোনটাই হতে পারে।
     
  4. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর যাতে  [ 1 to w ] পর্যন্ত সকল সংখ্যা কমপক্ষে একবার করে হলেও থাকবে। যেমনঃ A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} এবং w = 4, আমরা 13 length এর একটি সাব-অ্যারে পাবো, যাতে 1, 2, 3, 4 আছে। এই সেইম অ্যারের জন্যে যদি w = 3 হয়, তাহলে A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} আমরা 3 length এর একটি সাব-অ্যারে পাবো। 

সলুশন (Solution)
উপরের প্রবেল্মগুলি আমরা নরমালি বারে বারে লুপ চালায়ে সল্ভ করতে পারবো তখনি, যখন রেঞ্জ কম হবে, যা আমাদের given time এর মাঝে সল্ভ করা সম্ভব হয়। আমরা ব্রুটফোর্স এর ব্যাপারগুলি বাদ দিয়ে সরাসরি আমাদের স্লাইডিং উইন্ডো টেকনিক এ চলে আসি, যা কিনা O (n) সময়ে সল্ভ করতে সক্ষম।

১ম টেকনিক (First Technique):

আমরা প্রথমে উইন্ডো তে আমাদের প্রথম w টি ইন্টিজার ইন্সার্ট করে দিলাম এবং এদের সাম বের করে তাকে curr_sum ভ্যারিয়েবল এ রাখলাম। এরপরে আমরা স্লাইড করে করে আগাবো। আমরা ডান পাশে একটি একটি করে এলেমেন্ট উইন্ডো তে ইন্সার্ট করবো এবং বাম দিক থেকে একটি করে সরায়ে দিব, ফলে আমাদের উইন্ডোর সাইজ সেইম থাকবে।এলেমেন্ট ইন্সার্ট এর সময় আমরা চেক রাখবো যে এখন আমরা ম্যাক্সিমাম সাম পেলাম কিনা। প্রতিবার ইন্সার্ট করার সময় আমাদের নতুন সাম হবে curr_sum + inserted_element – removed_element. এভাবে আমরা পুরো অ্যারেকে স্লাইড করে রেসাল্ট পাবো। 

২য় টেকনিক (Second Technique):

যদি n এর মান অনেক বড় হয়, সকল সাব-অ্যারের মাক্স/মিন বের করা একটু কঠিন হবে। এজন্য আমরা deque (double ended queue) ব্যবহার করবো। এখন আমাদের উইন্ডো হবে আমাদের deque টি। আমরা deque কে ascending order ( ছোট থেকে বড় ) এ সাজাবো ( যদি মিন বের করতে চাই)। deque এর প্রথম দিকে আমাদের মিনিমাম এলেমেন্ট গুলি থাকবে। কিন্তু এভাবে কাজ করতে গেলে একটি বড় প্রব্লেম হল, আমাদের মূল অ্যারের ইন্ডেক্সগুলি উল্টাপাল্টা হয়ে যাবে, এজন্য আমাদের ইন্ডেক্স এর ট্র্যাক রাখতে হবে যাতে আমরা বুঝতে পারি যে, এলেমেন্ট উইন্ডো তে আছে কি নাই। নিচের একটি স্যাম্পল কোড দেয়া হল ঃ 

৩য় টেকনিক (Third Technique):

আমরা একটি ডাইনামিক সাইজ উইন্ডো মেইন্টেইন করবো, যেখানে ভ্যালু যোগ করতে থাকবো। মিন/ ম্যাক্স/ ইকুয়াল, কোন এক কন্ডিশন পেলে আমরা আমাদের মিনিমাম উইন্ডো সাইজ পেয়ে যাবো। প্রোগ্রাম এ কি চাওয়া হয়েছে তার উপরে ভিত্তি করে আমাদের কোড এ কন্ডিশন এর পরিবর্তন হবে। এখানে আমরা ১ম টেকনিক এর মত করে ইন্সার্ট করতে থাকবো এবং কন্ডিশন চেক করবো। আর এলেমেন্ট উইন্ডোতে আছে কিনা, উইন্ডো সাইজ কি আমাদের মূল অ্যারে থেকে বড় হয়ে গেলো কিনা – এসব আমরা ২য় টেকনিক এর মত একটি deque নিয়ে চেক করতে পারি।

৪র্থ টেকনিক (Fourth Technique):

আমরা এমন একটি উইন্ডো মেইন্টেইন করবো যা কিনা 1 to w সকল সংখ্যা যদি না পাই, উইন্ডো সাইজ বারাতে থাকবে, নাহলে সাইজ কমাতে থাকবে। আমরা মিনিমাম উইন্ডো সাইজের ট্র্যাক রাখবো। 1 to w সকল এলেমেন্ট পেয়ে গেলাম কিনা এটি আমরা নরমাল একটি ফ্রিকুয়েন্সি কাউন্টের মাধ্যমে করতে পারি। যখন সকল এলেমেন্ট এর কাউন্ট >0 হবে, তখন আমরা আমাদের মিনিমাম উইন্ডো সাইজ রিটার্ন করে দিবো।

প্র্যাক্টিস প্রব্লেম (Practice Problems): 

LightOj: Algebraic Problem

Problem Link: loj1070
Technique: Matrix Exponentiation

Given the value of a+b and ab you will have to find the value of an+bna and b not necessarily have to be real numbers. I solved this using matrix exponentiation technique. I will now write about how I modelled the base matrix for multiplication. There may be other approaches too. But first please read this blog if you don’t know about how to create a matrix from a recurrance relation.

First let’s observe some cases.
If n = 0, a0+b= 1+1 = 2
If n = 1, a1+b= a+b – 0
If n = 2, a2+b= (a+b) (a+b) – 2ab
If n = 3, a3+b= (a+b) ( (a+b)– ab ) – 2ab (a+b)
…………..     …………..     ………….     ……………..

So, basically the recurrence somehow turns like this –>

(a1+b1) = (a+b) + (-0)
(a2+b2) = (a+b) (a+b) + 2(-ab)
So,
base  =  | (a+b)   -ab  |
            |   1           0   |

We will multiply (a+b) with base [0][0] and 2 with base [0][1], then we will get our final output by summing these two elements.

So, when n = 0 , ans will be 2.
When n = 1, ans will be a+b
When n = 2, ans will be (base)= (a+b) * (a+b) + 2 * (-ab) = (a+b)2 – 2ab
When n = 3, ans will be (base)2  = (a+b) * [(a+b)2 -ab)] + 2 * [-ab*(a+b)]

Let’s see this : (for n = 3)
yo.jpg
In our base matrix, after performing exponentiation, at base [0][0] we get [(a+b)2 -ab)], and we will multiply it with (a+b). Similarly, at base[0][1] we get [-ab*(a+b)], so we will multuply it with 2. And by summing these two elements, we will get our final output.

NOTE : As For each test case, print the case number and (an+bn) modulo 264, we will use unsigned long long for each variable instead of applying modulus operation. This will save our time. Infact, without this, the program will get TLE.

“Don’t directly copy code. First try to understand how each step works, then do your own coding.”

HackerEarth: Fibonacci with GCD

Problem: Fibonacci with GCD

Editorial: It’s a segment tree problem with simple matrix exponentiation for generating fibonacci numbers. In this problem, we will be given some numbers. Then we will be asked to perform some queries.  Each query there will be a range, from that range we need to find GCD of all the elements fibonacci numbers. Say for 2 4 8, we need to calculate GCD ( fib[2], fib[4], fib[8] ) = GCD ( 1, 3, 21 ) = 1.

We will create a segment tree, where we will store the gcd of every elements of the array. Basically our segment tree will be made of calculating gcd for a given range. Then for the query we will calculate part by part in the range for our gcd. If left and right both child node is -1, then we will simply return 1. If left child is -1 but right child has positive value, then we will return right child. Similarly we will do for the right child being -1 also. And when both the child have positive value, we will return the gcd between them. After getting the gcd value from the elements of the range from our query, then we will find the fibonacci number of that gcd value. We will do that with matrix exponentiation.

So, basically, for this problem, we will create segment tree first with corresponding gcd, and then after the query, we will calculate the fibonacci number. Say for values : 2, 4, 8, the GCD = 1. So our answer will be fibonacci [ 1 ] and that is 1. ( Fibonacci series : 1, 2, 3, 5,….).

CF: Squares and not squares

Problem Link: Squares and not squares
Editorial: At first we can pre compute square numbers from 0 to 31623, as 31623*31623 = 1000014129, which is greater than 109.
Then we will take two seperate vectors, one for storing square numbers and other for non square numbers. We can store them at the time of taking input. Simply binary searching in the pre computed square numbers vector would be greate.
Now, we will count how many square numbers are there in the square vector. Say it is count1. And number of non squared number would be count2 = n – count1. Now–>

  1. If count1 == n/2, then the answer is zero.
  2. If count1 > n/2, then we need to make some of our squared numbers into non squared number.
  3. If count1 < n/2, then we need to make some of the non squared number to squared number.

count1 > n/2:
We need to check what is the maximum number of the squared numbers. If max_value is <=0, then for each squared number to make a non squared number we need to add +2 if the number is zero (0) else +1.
For 0, we should add +2 to make it 2, as 2 is not a squared number, but 1 is a square number. And we need to make (  count1- n/2 ) non_squared numbers.

count1 < n/2:
Now we need to find the closest squared number for each element of our non squared vector. Simply iterate through all the values from non squared vector and we will find upper_bound of each element in our pre computed square vector. We will take another vector to store the minimum value we got from each element via upper_bound. Finally we will sort the vector, and print the sum of the first (  n/2 – count1 ) elements from that vector.

Here is the solution of mine : solution

Even the Odds!

Contest link: Intra AUST Preliminary Fall – 17
Problem name: Even the Odds!

Required knowledge: Modular arithmetic, big multiplication.

Editorial: Firstly, try reading this Modular Arithmetic or you can google about modular arithmatic and it’s properties. Now let’s analyze the problem.
Given and M, we need to find summation of first even numbers modulo and summation of first odd numbers modulo M.

We can observe that the first N odd numbers summation can be found by calculating N * N and first N even numbers summation can be found by calculating N * (N+1).
let, N = 4,

Odd : 1 + 3 + 5 + 7 = 16 = 4 * 4
Even : 2 + 4 + 6 + 8 = 20 = 4 * 5

As the modulo M is really big we can’t simply calculate ( (N % M) * ( (N+1)%M) )%M, because the N can be as large as 1018 – 1 and M can be 1018, then at the time of multiplying, it will overflow. How can we do this without overflow? We will simply use a divide and conquer technique to calculate N * N by adding N with N, N times, instead of multiplying them. Let N = 1018 – 1, M = 1018.

Now, from modular arithmatic we know that

– (a * b) % m = (( a%m ) * ( b%m ))%m
– (a + b) % m = (( a%m ) + ( b%m ))%m

Say, = 1018 and b = 10 and m = 1018 – 1.
So, ( (1018 – 1) %1018 ) * (1018 – 1) %1018 ) ) % 1018= ( (1018 – 1) * (1018 – 1) ) % 1018 = 0 ; here 
(1018 – 1) * (1018 – 1) will cause overflow.

But,(((1018 – 1)%1018) + ((1018 – 1)%1018) + ….

We can easily add (1018 – 1 + 1018 – 1) and then mod it with 1018. We will do this 1018 times, and by using modulo operation each time, there won’t be any overflow.
As 1018 is also a very big number, we can do this is O (log10(N)) times with folowing divide and conquer algorithm.


We will use this bigmul function to calculate ( a * b ) % c. We will simply add the number a, b times each with modulo operation. As the range is too big, we can’t simply use loop, so we will use this recursion technique of calculating big multiplication in logN time.