Computing Binomial Coefficients i.e C(n,k)

There are many problems where we have to compute C(n,k) i.e  ( (n!)/( (n-k)! *(k!) ) ).
However,
computing C(n, k) can be a challenge when n and/or  k are large. There are several tricks
like: Making k smaller (if k > n − k, then we set k = n − k) because n C k = n C (n−k) .
 During intermediate computations, we divide the numbers first before multiply it with the
 next number; or use BigInteger technique (last resort as BigInteger operations are slow).
But there is another method to which we all are familiar but don't actually remember .
We can use  Pascal’s Triangle, a triangular array of binomial coefficients. The leftmost and
rightmost entries at each row are always 1. The inner values are the sum of two values directly
 above it, as shown for row n = 5 below : The value of ith entry of line number n is C(n,i);

          1               n= 0
        1   1             n= 1
      1   2   1           n= 2
    1   3   3   1         n = 3
   1  4   6   4   1       n = 4
 1  5   10  10  5   1     n = 5

The value of ith entry of line number n is C(n,i).
The below given code implements the formation of the pascal's triangle using a 2D array of size n*n.
The time complexity is of O(n^2) ,  but it's better than the general method of computing C(n,k) using multiplication.

#include<iostream>
#include<stdio.h>
using namespace std;

void printPascal(int n)
{
  int arr[n][n];
  for (int line = 0; line <= n; line++)
  {
    // Every line has number of integers equal to line number
    for (int i = 0; i <= line; i++)
    {
      // First and last values in every row are 1
      if (line == i || i == 0)
           arr[line][i] = 1;
      else // Other values are sum of values just above and left of above
           arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
      printf("%d ", arr[line][i]);
    }
    printf("\n");
  }
}
int main()
{
  printPascal(5);
}
output :

1  
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 

See this  triangle for understanding the above given code.

After going through the above topic ,  go through this link , and  first try to solve this question using bit shift operator (<<) . Why are you getting wrong answer ? Try using pow() function.You would be getting correct answer . To know the difference  between pow(2,n ) and  1<<n , go through This Link

Thank you and keep coding :)

Bitset in STL and Algorithms for finding Prime numbers

Hello  Guys ,
   Let's talk about the mathematics used in coding contests , like checking for prime numbers, finding prime factors , LCM , GCD ,Factorials  e.t.c
In this post I will be talking about an easy method to check whether a number is prime or not . For this I will be using  the famous  algorithm " Sieve of Eratosthenes" invented by Eratosthenes of Alexandria.

Before moving further I would like you to know what is 'bitset' . If you are familiar with this , you can jump to the next topic .

A bitset stores bits (elements with only two possible values: 0 or 1 , i.e true or false ). It  is an array of bool but each Boolean value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only, so space taken by bitset bs is less than that of bool bs[N] and vector bs(N)  i.e  each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char).
Due to this single bit , the operation performed on bitset is faster than that of array and vector . We can access the element of bitset just like an index of an array or vector . But there is a major difference between bitset and array .
bitset starts its indexing backward that is for 10110, 0 are at 0th and 3rd indices whereas 1 are at 1st 2nd and 4th indices.

The following code explains most of the basic member functions of bitset and there usage :

#include<iostream>
#include<bitset>
#define M 32
using namespace std;
int main()
{

// default constructor initializes with all bits 0
    bitset<M> bset1;
     // bset2 is initialized with bits of 20
    bitset<M> bset2(20);

    // bset3 is initialized with bits of specified binary string
    bitset<M> bset3(string("1100"));

    // cout prints exact bits representation of bitset
    cout << bset1 << endl;  // 00000000000000000000000000000000
    cout << bset2 << endl;  // 00000000000000000000000000010100
    cout << bset3 << endl;  // 00000000000000000000000000001100
    cout << endl;

    // declaring set8 with capacity of 8 bits

    bitset<8> set8;    // 00000000

    // setting first bit (or 6th index)
    set8[1] = 1;    // 00000010
    set8[4] = set8[1];   //  00010010
    cout << set8 << endl;

    // count function returns number of set bits in bitset
    int numberof1 = set8.count();

    // size function returns total number of bits in bitset
    // so there difference will give us number of unset(0)
    // bits in bitset
    int numberof0 = set8.size() - numberof1;
    cout << set8 << " has " << numberof1 << " ones and "
         << numberof0 << " zeros\n";

    // test function return 1 if bit is set else returns 0
    cout << "bool representation of " << set8 << " : ";
    for (int i = 0; i < set8.size(); i++)
        cout << set8.test(i) << " ";

    cout << endl;

    // any function returns true, if atleast 1 bit
    // is set
    if (!set8.any())
        cout << "set8 has no bit set.\n";

    if (!bset1.any())
        cout << "bset1 has no bit set.\n";

    // none function returns true, if none of the bit
    // is set
    if (!bset1.none())
        cout << "bset1 has all bit set\n";

    // bset.set() sets all bits
    cout << set8.set() << endl;

    //  bset.set(pos, b) makes bset[pos] = b
    cout << set8.set(4, 0) << endl;

    // bset.set(pos) makes bset[pos] = 1  i.e. default
    // is 1
    cout << set8.set(4) << endl;

    // reset function makes all bits 0
    cout << set8.reset(2) << endl;
    cout << set8.reset() << endl;

    // flip function flips all bits i.e.  1 <-> 0
    // and  0 <-> 1
    cout << set8.flip(2) << endl;
    cout << set8.flip() << endl;

    // Converting decimal number to binary by using bitset
    int num = 100;
    cout  << "\nDecimal number: " << num
         << "  Binary equivalent: " << bitset<8>(num);
  cout<<endl;
    return 0;
}

Output :

00000000000000000000000000000000
00000000000000000000000000010100
00000000000000000000000000001100

00010010
00010010 has 2 ones and 6 zeros
bool representation of 00010010 : 0 1 0 0 1 0 0 0
bset1 has no bit set.
11111111
11101111
11111111
11111011
00000000
00000100
11111011

Decimal number: 100 Binary equivalent: 01100100


Now coming back to our initial discussion regarding  prime numbers :

First, this Sieve algorithm sets all numbers in the range to be ‘probably prime’ but set
numbers 0 and 1 to be not prime. Then, it takes 2 as prime and crosses out all multiples
of 2 starting from 2 × 2 = 4, 6, 8, 10, . . . until the multiple is greater than N. Then it takes
the next non-crossed number 3 as a prime and crosses out all multiples of 3 starting from
3 × 3 = 9, 12, 15, . . .. Then it takes 5 and crosses out all multiples of 5 starting from 5 × 5 =
25, 30, 35, . . .. And so on . . .. After that, whatever left uncrossed within the range [0..N]
are primes. This algorithm does approximately (N× (1/2 + 1/3 + 1/5 + 1/7 + . . . + 1/last
prime in range ≤ N)) operations. The time complexity is of roughly O(N log log N).
Generating a list of primes ≤ 10K using the sieve is fast , we opt to use sieve for smaller
 primes and for the larger prime numbers we use other methods which I will be discussing later .
 The code is as follows:

#include <bitset>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
long long int _sieve_size;
bitset<10000010> bs; // 10^7 should be enough for most cases
vector<long long int> primes; // compact list of primes in form of vector<int>

void sieve(long long int upperbound)
{  
  // create list of primes in [0..upperbound]
_sieve_size = upperbound + 1; // add 1 to include upperbound
bs.set(); // set all bits to 1
bs[0] = bs[1] = 0;// except index 0 and 1
for (long long int  i = 2; i <= _sieve_size; i++)
{
if (bs[i])
{
// cross out multiples of i starting from i * i!
for (long long int j = i * i; j <= _sieve_size; j += i)
{
bs[j] = 0;
}
primes.push_back((int)i);
// add this prime to the list of primes
}
}
}

bool isPrime(long long int N)
{
// a good enough deterministic prime tester
if (N <= _sieve_size) return bs[N];
// O(1) for small primes
cout<<(int)primes.size()<<endl;
for (int i = 0; i < (int)primes.size(); i++)

if (N % primes[i] == 0) return false;
return true;
// it takes longer time if N is a large prime!
}
// note: only work for N <= (last prime in vector  "primes")^2
// inside int main()
int main()
{


sieve(10000000);
// can go up to 10^7 (need few seconds)

printf("%d\n", isPrime(2147483647));
// 10-digits prime
printf("%d\n", isPrime(136117223861LL));
// not a prime, 104729*1299709
//How are we checking this for number which are > 10^7 ??
//Actually we cn check upto prime numbers < (10^7)^2!!! using this method
//because to check whether a number is prime number or not , all we need to check whether
// the number has any factor less than (number)^(0.5) or not

}

Thank you.Keep Coding :)

Priority_Queue in STL

Hello guys , This time I am gonna tell you about priority_queue.

Priortiy_queue is a container adaptor,meaning that it is implemented on top of some underlying container type. By default that container
is Vector but a different type can be used too.

Before moving on i would like you to tell what is a Max_Heap:
please go to this link if you know nothing like JOHN SNOW about HEAP

priority_queue is just like a normal  queue except the element removed from the queue is always the greatest among the all the elements of the queue , thus this
container is usually used to replicate Max Heap in C++ .  Elements in Priority_queue can be inserted or removed in a time complexity of O(log(n)).

functions used :
 1. empty()
 2. size()
 3. top()
 4.push_back()
 5. pop_back()
 6. make_heap()
 7. push_heap()
 8. pop_heap()
 9. reverse()
 10.swap(x,y) -> exchanges the content of X and Y . X and Y are the priority_queue containers of the same type. Their size may be different
 11.compare -> used to determine whether one element is greater than the other element or not.
 if Compare(x,y) is true , then x is smaller than y

We can use any kind of container to store a priority_queue like , map , queue , dequeue etc
We can reverse the priorities also

example :

Here we are making a Heap without using a priority_queue
//make_heap,push_heap,pop_heap,reverse: -> all are included from #include<algorithm> */


#include<iostream>
#include<algorithm>
#include<queue>
#include <vector>
using namespace std;
int main()
{
    int myints[] ={10,20,30,5,15};
    vector<int>v(myints,myints+5);
    make_heap(v.begin(),v.end());
    cout<<"initial  max heap: "<<v.front()<<endl;
    pop_heap(v.begin(),v.end());
    v.pop_back(); // pops the last elemnt from the vector
    v.push_back(99);
    push_heap(v.begin(),v.end());
    cout<<"max heap after push: "<<v.front();
    sort_heap(v.begin(),v.end()); // sorts th element of the heap
    cout<<"final sorted range: ";
    for(int i =0;i<v.size();i++)
    {
        cout<<v[i]<<endl;
    }
    reverse(v.begin(),v.end()); // now the vector is reversed

    for(int i =0;i<v.size();i++)
    {
        cout<<v[i]<<endl;
    }
}}

/*The most important property of priority_queue is that it  does not allow iterations through its elements */
#include<iostream>
#include<queue>
 using namespace std;
 int main()
 {
    priority_queue<int>pq;
    priority_queue<int>zz;
    pq.push(10);
     pq.push(30);
    pq.push(40);
    pq.push(90);
    pq.push(100);
    pq.push(60);
    pq.push(10);
     zz.push(200);
     zz.push(530);
    zz.push(420);
    zz.push(910);
    zz.push(105);
    zz.push(160);
    zz.push(80);
    cout<<pq.size()<<endl;
    cout<<pq.top()<<endl;
    pq.pop();
    cout<<pq.top()<<endl;
    pq.pop();
    cout<<pq.top()<<endl;
    pq.pop();
    cout<<pq.top()<<endl;
    pq.pop();
    cout<<pq.top()<<endl;
    pq.pop();

 }

    /* Use of Swap() in priority_queue: */
#include<iostream>
#include<queue>
 using namespace std;
 int main()
 {
    priority_queue<int>pq;
    priority_queue<int>zz;
    pq.push(10);
     pq.push(30);
    pq.push(40);
    pq.push(90);
    pq.push(100);
    pq.push(60);
    pq.push(10);
     zz.push(200);
     zz.push(530);
    zz.push(420);
    zz.push(910);
    zz.push(105);
 
    swap(pq,zz);
    cout<<"size of pq: "<<pq.size()<<" size of zz: "<<zz.size()<<endl;
}
/*  if we can create heap using make_heap , push_heap and pop_heap  then why do we use priority_queue ??
    it  is because of the restriction of iteration of element in priority_queue
 **** Have you ever wondered why pop() returns void instead of  value_type ??
     

*/
/* A priority_queue for user defined objects :->
  *** priority_queue  can be used in many real life situations also
    for example :
*/

#include<iostream>
#include<queue>
#include<vector>
    class Toast
{
    public :
        int bread;
        int butter;
        Toast(int bread ,int butter)
            :bread(bread),butter(butter)
            {
            }
 };

// how  will you sort a toast given that toast has a value based upon the amount of butter and bread.
//This is done by creating a structure implementing an operator() and efficiently doing less than comparision

struct ToastCompare
{
    bool operator()(const Toast &t1 ,const Toast &t2)const
    {
        int t1value = t1.bread*1000 + t1.butter;
        int t2value = t2.bread*1000 + t2.butter;
        return t1value<t2value;
    }
};


using namespace std;
int main()
{
    Toast toast1(2,200);
    Toast toast2(1,300);
    Toast toast3(1,10);
    Toast toast4(3,1);
   
    priority_queue<Toast,vector<Toast>,ToastCompare>q;
    q.push(toast1);
    q.push(toast2);
    q.push(toast3);
    q.push(toast4);
    while(!q.empty())
    {
        Toast t = q.top();
        cout<<"bread: "<<t.bread<<"  butter: "<<t.butter<<endl;
        q.pop();
    }

}

c++ stl map

Hello everyone!

This time I am going to tell you about  MAP -> a very very important stuff that saves lot of your time during a coding contest .
Just like stack , queue ,      map is also a container class of STL .

A map contains two values , one of them is the key and other is the value stored at that key . A particular value can be accessed or modified by using its key . A key of a value is unique i.e map has unique keys which can not be modified .
following example will clarify everything :

#include<iostream>
#include<string.h>
#include<string>
#include<map>

using namespace std;

int main()
{
     map<string,int>employees;   // here the first one(string) is the key and int is the value stored at
                                                   //at that key
     employees.insert(pair<string,int>("vikram",1932)) ; //inserting values into map
      employees.insert(pair<string,int>("Rahul" ,1231)) ;
     employees.insert(pair<string,int>("arjun" ,1012)) ;
 
     cout<<"map size : "<<employees.size()<<endl; // to get  the size of map
     // iterating thorugh a map
    // In STL iterators provide a means for accessing data stored in container classes such a vector
   //  list , map etc .
    // declaring an iterator ->  class_name<template_parameters>::iterator name
   map<string,int>::iterator it = employees.begin(); // referencing iterator to the beginning of map
   for(it; it!= employees.end() ; it++ )
   {
         cout<< it->first<<"  "<<it->second<<endl;  // first gives  you the key ,, second gives you value
   }cout<<endl;
    //iterating the map in reverse manner
 
    map<string,int>::reverse_iterator  bt =  employees.rbegin();
   for(bt ;  bt!= employees.rend(); bt++)
   {
         cout<< bt->first<<"  "<<bt->second<<endl;
   }



   /*  to check whether a key is present in the map */
   // suppose we want to check  if  a key named "arjun" is present in the map or not
   // for this we use map.count(key_name) ;  it returns value >0 if that key is already in map else 0

   if( employees.count("arjun")>0){cout<<"this key is present "<<endl; }
 
      /*  accessing/modifying  value stored at a particular key*/
      // accessing :
      cout<<"value stored at arjun : "<<employees.at("arjun")<<endl;
     //modifying :
      employees.at("arjun") = 500;
    // inserting new key using [ ] :
     employees ["tata"] = 123;
      cout<<"value stored at tata : "<<employees.at("tata")<<endl;
 
 }

output is :
map size : 3
Rahul  1231
arjun  1012
vikram  1932

vikram  1932
arjun  1012
Rahul  1231
this key is present
this key is present
value stored at arjun : 1012
value stored at tata : 123

  

you can see that value stored in a map is already sorted . Time complexity of std:: map is of log(n)

I will be writing about tie complexity in another post .

If regarding map you have any doubt , visit this page this one

Here are some questions which can be solved using map . Please go through this link  if you hate Ramsay Bolton and enjoyed the Battle of Bastards :) 

c++ stl map

Hello everyone!

This time I am going to tell you about  MAP -> a very very important stuff that saves lot of your time during a coding contest .
Just like stack , queue ,      map is also a container class of STL .

A map contains two values , one of them is the key and other is the value stored at that key . A particular value can be accessed or modified by using its key . A key of a value is unique i.e map has unique keys which can not be modified .
following example will clarify everything :

#include<iostream>
#include<string.h>
#include<string>
#include<map>

using namespace std;

int main()
{
     map<string,int>employees;   // here the first one(string) is the key and int is the value stored at
                                                   //at that key
     employees.insert(pair<string,int>("vikram",1932)) ; //inserting values into map
      employees.insert(pair<string,int>("Rahul" ,1231)) ;
     employees.insert(pair<string,int>("arjun" ,1012)) ;
 
     cout<<"map size : "<<employees.size()<<endl; // to get  the size of map
     // iterating thorugh a map
    // In STL iterators provide a means for accessing data stored in container classes such a vector
   //  list , map etc .
    // declaring an iterator ->  class_name<template_parameters>::iterator name
   map<string,int>::iterator it = employees.begin(); // referencing iterator to the beginning of map
   for(it; it!= employees.end() ; it++ )
   {
         cout<< it->first<<"  "<<it->second<<endl;  // first gives  you the key ,, second gives you value
   }cout<<endl;
    //iterating the map in reverse manner
 
    map<string,int>::reverse_iterator  bt =  employees.rbegin();
   for(bt ;  bt!= employees.rend(); bt++)
   {
         cout<< bt->first<<"  "<<bt->second<<endl;
   }



   /*  to check whether a key is present in the map */
   // suppose we want to check  if  a key named "arjun" is present in the map or not
   // for this we use map.count(key_name) ;  it returns value >0 if that key is already in map else 0

   if( employees.count("arjun")>0){cout<<"this key is present "<<endl; }
 
      /*  accessing/modifying  value stored at a particular key*/
      // accessing :
      cout<<"value stored at arjun : "<<employees.at("arjun")<<endl;
     //modifying :
      employees.at("arjun") = 500;
    // inserting new key using [ ] :
     employees ["tata"] = 123;
      cout<<"value stored at tata : "<<employees.at("tata")<<endl;
 
 }

output is :
map size : 3
Rahul  1231
arjun  1012
vikram  1932

vikram  1932
arjun  1012
Rahul  1231
this key is present
this key is present
value stored at arjun : 1012
value stored at tata : 123

  

you can see that value stored in a map is already sorted . Time complexity of std:: map is of log(n)

I will be writing about tie complexity in another post .

If regarding map you have any doubt , visit this page this one

Here are some questions which can be solved using map . Please go through this link  if you hate Ramsay Bolton and enjoyed the Battle of Bastards :) 

2.) Stack

Hello guyz ,  this  time  I am writing about Stacks in c++

Stack is one  of  the data structures which is also a container of C++ stl .  
We all  have seen somewhat use of  stack in our day to day life . For more clarity , Let's assume there is a pile of plates in a party i.e one plate is on the  top of the other. If someone needs a plate , He removes the plate which is  on the top And if someone wants to add a plate in that pile He pus it on the top . So this is  a practical example of a stack.
Stack has the property of LIFO i.e the Last element is the First one to  come out as it was there in the previous example of  pile of the plates .

In programming word  -- Stack is an area of memory that holds all local variables and parameters used by any function, and remembers the order in which functions are called so that function returns occur correctly.
 Each time a function is called, its local variables and parameters are “”pushed onto”” the stack.
When the function returns, these locals and parameters are “”popped.””
Because of this, the size of a program’s stack fluctuates constantly as the program is running, but it has some maximum size.
A Stack has mainly two operations 1.)Push      2.)Pop

There are  many questions in competitive coding  where we need to implement Stack .

I will show the implementation of  stack in c++ stl . If you want to see the basic  coding  of implementing a stack ,, google it :) .

#include <iostream>      

#include <stack>          // we need  to implement the stack from stl library 

using namespace std;

int main ()

{

  stack<int> mystack;                    // you  can  store  any type of data 

  for (int i=0; i<5; ++i) 

{

       mystack.push(i);                     // push()   function puts data on the top of other in stack

}

cout << "Popping out elements...";

  while (!mystack.empty())                  //  returns true if  your stack is not empty

  {

     std::cout << ' ' << mystack.top();       // the top  value on the  stack  is accessed by .top() function

     mystack.pop();                                //  removes out the top value  present in the stack  thus making the next one element                                                              //the top one 

  }

  std::cout << '\n';

  return 0;

}

output :   4 3 2 1 0

If you want to practice questions regarding stack ,, google some of the tagged question  with stack .  while you  can try this one . This is a very good and easy  question regarding implementation  of stack  -  try this

Learning STL in C++ -- 1.) Pair

Hello friends
     These  days I spent  my time learning about STL (Standard Templae Library) in C++ .
Actually STL is  a software library in C++ .It has  mainly four components  namely , Algorithms , Functional , Containers , Iterators .
Out  of  which , I found  Algorithms  and Containers very useful and am still learning them.
C++ STL is very vast and very very  useful and  user friendly .

First of  All I  would  like  to tell you about Containers .
They are the Objects that store data. The standard Sequence  Containers include : Vector , Deque , Stack, List
The standard associative Containers are Set , Multiset , Map
There are  also other Containers like Pair , hash_set etc.

1.) Pair : It is a simple associative container  which can store two  types  of  data together . These two types  of  data are called as 'first' and 'second' respectively  .
To use pair and its methods we include utility library .

Here is an Example  showing basic  usage of pair in c++ :



#include <iostream>
#include <utility>
using namespace std;
int  main()
{
    int  n = 1;
    int a[5] = {1, 2, 3, 4, 5};

    // build a pair from two ints
    pair<int,int> p1 = std::make_pair(n, a[1]);
    std::cout << "The value of p1 is "
              << "(" << p1.first << ", " << p1.second << ")\n";
}
we can  use  any two  different  data types to  store in pair .

Pair has many uses in other containers , that i will explain later .

Meanwhile there is an important keyword named auto  in C++ 11 and onwards  Go through This link  to  know  about  it . Its very useful in certain cases .

JavaBIgInteger - A very important tool

Hello everybody !!
It has  been long  since  i  wrote something on my  blog .

I had  to take a gap due to my exams and vacations . This time i am gonna tell you about the benifits of Biginteger class of  java .
BigInteger class of java can be imported from math class of java . There are  several benifits of using BigInteger class which puts the java  user a way ahead  than C/c++ users in  certain aspects.
For Example : if  you are  required to find 25! ,,  there  are  no  any  built in data types in C/c++ which can store such a big value.
If you try finding 25! using C/C++ ,  it  would take you very complex method  to  do so . Fortunately we can solve it  easily in Java using BigInteger .

BigInteger class supports basic integer operations  in it . Some of the useful methods are :
addition : add(BI)  //BI-> BigInteger type
substraction : substract(BI)
multiplication : multiply(BI)
divide : divide(BI)
remainder : remainder(BI)
modular : mod(BI)

 javaBigInteger has several other  bonus features that can be useful during programming
contests—in terms of shortening the code length—compared to if we have to write these
functions ourselves. Java BigInteger class happens to have a built-in base number converter:
The class’s constructor and function toString(int radix), a very good (but probabilistic)
prime testing function isProbablePrime(int certainty), a GCD routine gcd(BI), and a
modular arithmetic function modPow(BI exponent, BI m)

the  following  program shows how to calculate 25! using BigInteger :

import java.util.*;
import java.math.*;

class Factorial{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= 25,i,j,k;
BigInteger product = BigInteger.ONE;// BigInteger has special cnstants like ZERO,ONE,TEN etc
for(i=1;i<=n;i++)
{
product = product.multiply(BigInteger.valueOf(i)); // here we cant write i directly ,, coz integer needs to be typecasted in BigInteger here

}
System.out.println("The value of your faactorial is  = " + product);

}
}


Base number conversion using BigInteger :
given a base b and two  positive integers p and m in base b.We have to compute p%m in base b .
i.e if we have b=2 , p = 110 ,m = 011 .  answer should be 010 . i.e 5%3 = 2.
the following solution explains this :

class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int b = sc.nextInt();
if (b == 0) break; // special class’s constructor!
BigInteger p = new BigInteger(sc.next(), b); // the second parameter
BigInteger m = new BigInteger(sc.next(), b); // is the base
System.out.println((p.mod(m)).toString(b)); // can output in any base
} } }

Modular Exponentiation

Yesterday i came through a question where , the user was asked to compute  modulus of exponential value of a number raised to power of a big number.  For example let , b =4,e=13, m =497.  we have  to  find c. where   c = (b^e)%m  .  obviously its time taking   to compute   (b^e).  
Here is the question :   question link

Note that b is only one digit in length and that e is only two digits in length, but the value b^e is 8 digits in length. i.e  b^e   =  67,108,864.   but  what happen  when ,, Consider b = 5 × 10⁷⁶ and e = 17, both of which are perfectly reasonable values. In this example, b is 77 digits in length and e is 2 digits in length, but the value b^e is 1,304 decimal digits in length. Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to slow considerably. 

 There are three methods  to compute this value :

1.) first one  is  the basic  one . i.e   calculate b^e and then take its modulus with m .

2.) Memory Efficient : this method requires much more operations than the previous method  but  it is much  better  and less time consuming  than  the previous one . The algorithm for the second one is 

if   c can be expressed as ,  c = a.b ,

 then :

c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod m

The algorithm is as follows:

1. Set c = 1, e′ = 0.
2. Increase e′ by 1.
3. Set c = (b ⋅ c) mod m.
4. If e′ < e, go to step 2. Else, c contains the correct solution to c ≡ b^e mod 'm.

Note that in every pass through step 3, the equation c ≡ b^e′ mod m holds true. When step 3 has been executed e times, then, c contains the answer that was sought. In summary, this algorithm basically counts up e′ by ones until e′ reaches e, doing a multiply by b and the modulo operation each time it adds one (to ensure the results stay small).

The example b = 4, e = 13, and m = 497 is presented again. The algorithm passes through step 3 thirteen times:

• e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
• e′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
• e′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
• e′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
• e′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
• e′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
• e′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
• e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
• e′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
• e′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
• e′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
• e′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
• e′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.

The final answer for c is therefore 445, as in the first method.

Try  to  visualize the  solution  step by step on  your  own using the above algorithm .

The time taken  to compute this one  is much less as  compared to  the first method.

3.) Right to left binary method :

This method  is more efficient than above given  two methods as well  It is a combination of the previous method and a more general principle called exponentiation by squaring (also known as binary exponentiation). and the number of operations is equal to the number of digits in binary representation  of the exponential .

first of all convert  e  in binary form . i.e for e = 13 , its binary equivalent is 1101 . store this in an array . i.e arr[3] = 1 , arr[2] = 1 , arr[1] = 0, arr[0] = 1 .

The implementation of  this method is as  follows :

set, result=1, and base=b,j=0;  

    while(j<=size of array) 

    {

if(arr[j]==1)

    {

      result = (result * base) % m;

    }

j++;

        base = (base*base)% m;;

    }cout<<result<<endl;

Try  to implement  these methods on  your  own ,  because  that is  the only way  you are gonna learn  things . I am doing the same things ,  share  knowledge, it helps you to learn more and more :) keep coding 

GCD (Greatest Common Devisior) Algorithms :

We All know what Gcd of two numbers is . There are many questions in which we require to implement the Gcd algorithm . There  are many ways to  find Gcd between two numbers . But we prefer those methods which are more efficient .

 The most basic and best method or algorithm is that one to which we all  are familiar . i.e. Euclid's gcd algorithm :
suppose  there are two numbers a and b of which we need to find the Gcd . We  can implement this either by making a recursive function or by making 'for' loops in your program. But generally recursion is  better than making loops . The code for  the Ecluid's  Gcd goes here :

#include <stdio.h>

int gcd_algorithm(int x, int y)
{
    if (y == 0) {
        return x;
    } else  {
        return gcd_algorithm(y, (x % y));
    }
}

int main(void)
{
    int num1, num2, gcd;
    printf("\nEnter two numbers to find gcd using Euclidean algorithm: ");
    scanf("%d%d", &num1, &num2);
    gcd = gcd_algorithm(num1, num2);
    if (gcd)
        printf("\nThe GCD of %d and %d is %d\n", num1, num2, gcd);
    else
        printf("\nInvalid input!!!\n");
    return 0;
}

  tr to understand this by going step by step in the recursion.

NOW TRY TO FIND GCD OF TWO NUMBERS WHEN ONE OF THEM IS EXTREMELY LARGE :

Suppose numbers  are A and B ,  where A can be  upto 10^250 and B upto 40000 . obviously long long int  can't store A . for better understanding of  this  problem  try  :      https://www.codechef.com/problems/GCD2

  

THERE IS A VERY MISCHIEVOUS METHOD FOR STORING SUCH BIG NUMBERS . WE DO SO BY STORING THEM IN AN ARRAY OF INTEGERS .

FOR EXAMPLE THE ABOVE QUESTION  CAN BE DONE  AS :

Time complexity

So what do you mean by time complexity ???

Have you ever wondered why sometimes when you sub,it your code and the online judge gives you an error named TLE (Time Limit Error) ? This is what i am going to explain to you .
Its a simple way of measuring how much time your code or algorithm  is taking to output the result as  per the given input . The time complexity of algorithms is most commonly expressed using the big O notation.

Time Complexity is most commonly estimated by counting the number of elementary functions performed by the algorithm. And since the algorithm's performance may vary with different types of input data, hence for an algorithm we usually use the worst-case Time complexity of an algorithm because that is the maximum time taken for any input size. 

How do we measure it ?? 

While measuring the time complexity of a code , we don't consider the time taken by constants , or variable declaration as they very very less time as  compared to the whole program .

suppose part of a code is :

for(i=1 ; i <=n; i++ )

{

      statement ;

}

this statement will run N times . one time for each value of 'i' 

therefore this part of code will have a time complexity of O(n) .

We try to reduce time complexity of our code as much less as possible. For this we try to use better algorithms , alternate methods of input . Whenever stuck try to google alternate methods of the problem where you are stuck

There are some other time complexities such as O(log(n)) (in trees ) , O(nlog(n)) , O(n^2) (using 2 nested for loops) e.t.c .

So the main aim of every programmer is to reduce the time complexity so as to give a High performance of your code . 

Getting faster inputs

We generally use cin/scanf/getchar for  inputs. Let us talk about a new way of input.

getchar_unlocked()  :

 
 What is  getchar_unlocked () ?
 A function that gets a character from stdin. It returns the next character from stdin. If stdin is at the end of the file, the end of the file indicator is set then getchar_unlocked() returns EOF.
 In short, it is another version of getcha(). It is used only for high and very large inputs as it is not threaded safe.

What do we mean when we talk about thread safety?
A thread is an execution context i.e it is all about execution of events on a computer. Suppose you are using a book and want to take a break right now, but you want to be able to come back and resume the reading from the exact point where you stopped. One way to do so is by writing down the page number, line number and book number.So your execution context for reading book is these 3 numbers. If you have a friend and he is using the same technique,he can take the book while you are no using it, and resume reading from where he stopped.The you can take it back,and resume it from you were.
Threads work the same way. A CPU gives you the illusion that it's doing multiple computation at the same time. It does that by spending a bit of time on each computation. On a technical level, an execution context(thread) consists values of the CPU's registers.

Windows does not support getchar_unlocked() function. because it's thread unsafe. So if you  aren't  using Linux then the only possible way to use this is on an IDE.

Here  is  an example using getchar_unlocked():


The following function can be used to read both +ve and -ve integers using getchar_unlocked().

#include<iostream>
#include<stdio.h>


long long int get_num(long long int &num)
{
     num = 0;
    char c = getchar_unlocked();
    long long int flag = 0;
    while(!((c>='0' & c<='9') || c == '-'))
        c=getchar_unlocked();
    if(c == '-')
    {
        flag = 1;
        c=getchar_unlocked();
    }
    while(c>='0' && c<='9')
    {
        num = (num<<1)+(num<<3)+c-'0';
        c=getchar_unlocked();
    }
    if(flag==0)
        return num;
    else
        return -1*num;
}

int main()
{
  long long int number;
 number = get_num(number);
 printf("%lld\n",number);
}


The working of the function goes like this:
The first while loop keeps repeating until 'c' is given a value of a digit between 0-9 or '-'(in the case of negative numbers).
If we encounter '-', we initialize flag = 1 to make a note that it is a negative number.
The second while loop keeps repeating until 'c' gets a value between 0-9 and stops when any other character is read(Usually it would be a ' '(space) or '\n').
The statement num = (num<<3)+(num<<1)+c-'0'  turns character digit in c to integer digit and is added to num*10 (Left shift operators i.e num << a = num * (2^a) ).
It can also be written as:

num = num*10 + c-'0'
Finally, we return the value of num depending on the value of t flag(whether the number is -ve or +ve).

You can use the above function to read any data type. Just change the data type of the value you're passing into this function to the data type you want to scan.

 Try this question to see the difference between other input methods and getchar_unlcked():
https://www.codechef.com/problems/INTEST


Why do we use different methods of inputs?

In most of the cases, the answer is related to time complexity or the time taken to take the input. The time  is taken by different input methods increases in the following order:

getchar_unlocked < getchar < scanf < cin

The speed difference in scanf and cin is because iostream I/O functions maintain synchronization with the C library I/O functions. We can turn  this off with a call to
std::ios::sync_with_stdio(false); ( do this if you are going to use C++    I/O only).
So until and unless speed factor is too much necessary, or you see some message like
"Warning: Large I/O data"   try to avoid getchar_unlocked 

Starting...

 Those who tell you that learning a language or programming skill  or web development or any field of computer science  is  like a piece  of  cake or an overnight process, are  those idiots who  walk into  glass doors .  So assume it  that you would have to work hard and  give  max of   your time . Just changing your status   and wallpapers won't make you a star . It requires tremendous hard work and  passion to achieve your goals.

First of all you should know all the  basics  of  a programming  language and have a good practice in topics like handling  a loop , checking a condition , working with strings,pointers , matrices,functions etc.

Pick up any competitive coding site . There are many such  sites like Codeforces , a2oj , Uva ,Codechef, Hackerearth , Hackerrank, Spoj , Projecteuler etc.  I would suggest you to use Codeforces/Codchef/Hackerrank  as the questions  present there are conceptual and help you to enhance your coding skills .

Till now i have good practice in C , C++  and currently  learning Java .
Start from the Beginner level . Attempt those questions  first which  have maximum submissions.
Initially you would find it difficult to solve them . There are certain approach and certain tools  for meeting the required constraints of  problems . ......

1.) Taking an Input :

suppose you  have to check 'T' test   cases .
your code should start like this ..
int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
    // your code goes here .........
     ........
     ........
     output the result for each test case here like..
     printf("%d\n",answer);
   }
}

About Me

I am  in 2nd semester of my B.tech course and currently pursuing computer science from Thapar University . It has  been 8-9 months  since i  have  started coding and learning  data structures and Algorithms. I try my  best to  give  my  maximum  time to these fields . I love  to  learn  new things be  it music , science , sports , politics or anything . I love to share whatever knowledge i have gained so far . Its very difficult  for you to get over   your problems  and  find proper solutions for them , when  there is  no one other  than internet, to guide you . That's why i am  writing this blog  to help  those who face the same difficulties in  the initial stage  of  coding ....