Monthly Archives: August 2015

Euclids GCD Algorithm

Greatest Common Divisor- Euclid’s Algorithm

Problem:

Given two numbers M and N, find their GCD.

Example:

M=36  N=48
Answer: 12

Solution:

The GCD or Greatest common divisor of two numbers can be calculated using Euclid’s Algorithm for GCD which is given below:

while( n is not divisible by m)
{
     rem = n mod m;
     n=m;
     m=r;
}

The value of ‘r’ is the GCD required

Lets take an example, let m=36 and n=48,
48 is not divisible by 36, thus,

Iteration 1:
rem=12 (48%36)
n=36 ( Previous m)
m=12 (rem is 12)

Now, 36(n) is divisible by 12(m), thus, the loop will not work!
Coming onto the next equation after the loop, the value of ‘r (12)’ is the required answer.

Here is the working Code:

Iterative:

#include <stdio.h>
int main()
{
     int m,n,r;
     m=36; n=48;
     while(n%m)
 	{
 		r=n%m;
 		n=m;
 		m=r;
 	}
 	printf("%d",r);
 	return 0;
}

Recursive:

#include <stdio.h>

int gcd(int n,int m)
{ 
     if(n==0)
          return(m);
     else 
          return(gcd(m%n,n));
 }
 
int main()
{
     int m,n,r;
     m=36; n=48;
     r=gcd(n,m);
     printf("%d",r); 
     return 0;
}

Output:

12

Spoj SUMITR solution

Spoj SUMITR Solution. Spoj Sums In a Triangle Solution.

Category: DP, AdHoc

Here we store the maximum path sum value in a bottom-up manner.

Algorithm:

  1. Start from the second last row, last element.
  2. Add to it the maximum of the element below it and towards its right.
  3. Repeat the above steps, for each element, from right to left manner.
  4. Repeat the above steps for each row, till we reach the topmost  row,
  5. We have our answer in the 1st element of the 2-D array.

NOTE: The problem requires the solution to be less and 256 bytes.To take care of this, remove all tabs, spaces from the given code, and then submit it. The working code and the short-space removed code have been given below:

#include<iostream>
using namespace std;
main()
{
     int t,b[100][100],n,i=0,j;
     cin>>t;
     while(t--)
     {
          cin>>n;
          for(;i<n;i++)
               for(j=0;j<i+1;j++)
                    cin>>b[i][j];
          /*The actual action starts here*/
          
          for(i=n-2;i>=0;i--)
               for(j=0;j<i+1;j++)
                    b[i][j]+=b[i+1][j]>b[i+1][j+1]?b[i+1][j]:b[i+1][j+1];
          /*The above loops perform the steps of the Algo*/
          cout<<b[0][0]<<"\n";
     }
}

Here is the working code without spaces:

#include<iostream>
using namespace std;main(){int t,b[100][100],n,i=0,j;cin>>t;while(t--){cin>>n;for(;i<n;i++)for(j=0;j<i+1;j++)cin>>b[i][j];for(i=n-2;i>=0;i--)for(j=0;j<i+1;j++)b[i][j]+=b[i+1][j]>b[i+1][j+1]?b[i+1][j]:b[i+1][j+1];cout<<b[0][0]<<"\n";}}

Spoj WILLITST solution

Spoj WILLITST solution. Spoj Will It Ever Stop solution.

Category : AdHoc

This question is very simple if you get that the program will  stop only if the input number is a power of 2.

Thus all you need is to check if a number is a power or two or not. Read the link for detailed explanation.

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main() {
     LL n;
     scanf("%lld",&n);
     if((n&(n-1))==0)
          printf("TAK\n");
     else 
          printf("NIE\n");	
     return 0;
}

 

How to check if Number is a power of 2 or not

Problem:

Given a number we need to tell if it is a power of two or not?

Example:

Input: 8
Ans: Yes

Solution:

Here we just need to take Bitwise and (&) of N and (N-1),
if its 0, the YES else NO.

Explanation

For power of 2:

8 is represented in binary as 1000, and
7 is represented as 0111.

Taking bitwise & we get 8 & 7 = (1000)2&(0111)2 = (0000)2

for Non-power of 2:

7 =(0111)2
6=(0110)2

Taking bitwise & we get : (0111)& (0110)2= (0110)2 =6

Here is the working code:

#include <iostream>
using namespace std;

void Ispowerof2(int n)
{
     if(n&(n-1))
          cout<<"NO, not a power of 2\n";
     else
          cout<<"YES, power of 2\n";
}

int main() {
     Ispowerof2(8);
     Ispowerof2(7);
     Ispowerof2(16);
     return 0;
}

Output :

YES, power of 2
NO, not a power of 2
YES, power of 2

Spoj OLOLO solution

Spoj OLOLO solution. Spoj Onotole needs your help Solution.

Category : AdHoc

This question is the implementation of Find the Number Occurring Odd Number of Times.

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
     int n,k,ans=0;
     scanf("%d",&n);
     while(n--)
     {
          scanf("%d",&k);	
          ans^=k;
     }
     printf("%d\n",ans);
     return 0;
}

 

Spoj COLONY solution

Spoj COLONY Solution. Spoj Linearian Colony Solution.

Category:  Recursion

The sequence or tree described/given in this question is based on Thue-Morse Sequence.

Here we use recursion, considering zero-indexed variables (i.e. the first level is denoted by 0 and first element is also denoted by zero)

Algorithm:

  1. Set N==0 && k==0 as the base case, and return ‘R’ for it.
  2. calculate value of parent of the given element by dividing K by 2
  3. Get the answer for (Upper level (i.e. N-1), Parent (i.e. K/2))
  4. if parent*2 != K, then we have our answer,
  5. else we switch the answer to B if R and R if B.

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long

char Colony(LL n,LL k)
{
     /*Base Case*/
     if(!k && !n)
          return 'R';
          
     /*Calculating the index of the parent*/	
     LL parent=k/2;
     char ans=Colony(n-1,parent);
     
     /*If the parent is not equal to k/2, then
     switch the answer*/
     if(2*parent==k)
          ans=(ans=='R'?'B':'R');
     return ans;
}

int main() {
     LL n,k;
     scanf("%lld%lld",&n,&k);
     char ans=Colony(n,k);
     if(ans=='R')
          printf("red\n");
     else
          printf("blue\n");
     return 0;
}

Spoj DCEPC504 solution

Spoj DCEPC504 Solution. Spoj The Indian Connection Solution.

Category:  Recursion

The sequence or tree described/given in this question is somewhat inspired from Thue-Morse Sequence, but is not exactly the same.

Here we use recursion, considering zero-indexed variables (i.e. the first level is denoted by 0 and first element is also denoted by zero)

Algorithm:

  1. Set N==0 && k==0 as the base case, and return ‘M’ for it.
  2. calculate value of parent of the given element by dividing K by 2
  3. Get the answer for (Upper level (i.e. N-1), Parent (i.e. K/2))
  4. if parent*2 == K, then we have our answer,
  5. else we switch the answer to F if M and M if F.

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long

char IndianC(LL n,LL k)
{
     /*Base Case*/
     if(!k && !n)
          return 'M';
          
     /*Calculating the index of the parent*/	
     LL parent=k/2;
     char ans=IndianC(n-1,parent);
     
     /*If the parent is not equal to k/2, then
     switch the answer*/
     if(2*parent!=k)
          ans=(ans=='M'?'F':'M');
     return ans;
}

int main() {
     int t;
     scanf("%d",&t);
     LL n,k;
     while(t--)
     {
          scanf("%lld%lld",&n,&k);
          /*To convert the input to zero indexed,
          we subtract 1 from both N and K*/
          char ans=IndianC(n-1,k-1);
          if(ans=='M')
               printf("Male\n");
          else
               printf("Female\n");
     }
     return 0;
}

Spoj COINS solution

Spoj COINS solution. Spoj Bytelandian gold coins Solution.

Category : Recursion, DP

Approach 1 Recursion:

This is a very basic recursion problem. Keeping the time limit 9s of the question we do not recur on every possible sub path, but rather recur only when the sum of (N/2+N/3+N/4) is greater than N.

NOTE: This approach of selective calling on predicate basis may fail in many other questions and algorithms, but passes the test cases of this question. We would be more than happy  if you could provide us with a test case where this fails.

Here is the working code:

#include <stdio.h>

unsigned long int coins(unsigned long int n)
{
     unsigned long int a=n/2,b=n/3,c=n/4;	
     
      if (a+b+c>n)
          return coins(a)+coins(b)+coins(c);
     else return n;	
}

int main() {
     unsigned long int n;
     while(scanf("%lu",&n)!=EOF)
     {
          printf("%lu\n",coins(n));
     }
     return 0;
}

The above given approach is not optimal as after drawing the recursion tree, you might understand that the result of sub-problems is computed again everytime, even when they have been calculated in the past.

Thus, we can come up with a better solution.

Approach 2 Dynamic Programming (here Recursion + memoization):

Here we just store and use previous calculated results. We use STL map to do so.

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
map <LL,LL> ans;

LL coins(LL n)
{
     if(n==0)
          return 0;
     else if(!ans[n])
     {
          ans[n]= max(n,coins(n/2) + coins(n/3) + coins(n/4));
     }
     return ans[n];
}

int main() {
     LL n;
     while(scanf("%lld",&n)!=EOF)
     {
          printf("%lld\n",coins(n));
     }
     
     return 0;
}

 

Spoj FACTMUL solution

Spoj FACTMUL solution. Spoj Product of Factorials Solution.

Category : Number Theory

This question seems pretty straight forward at first sight, but then we realize that 109546051211 is not a prime number!
This number is product of two primes 109546051211= 186583 * 587117 .

Here thus we need to find Modulus with two prime numbers and thus, Chinese Remainder Theorem (CRT)  comes to the rescue!

Pre Requisite : Modular Exponentiation

Algorithm:

  1. we maintain two set variables, one for each prime number.
  2. one variable in each set maintains the factorial mod p till that number and other product of factorials mod p till that number.
  3. use CRT to get the final answer.
  4. The coefficients a1 and a2 for CRT would be respective products of factorials till that number (N).

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long

LL ModularExponentiaion(LL x,LL n,LL p)
{
       LL ans=1,temp=x%p;
       while(n)
       {
              if(n&1) // to check if last bit is 1 or not
              {
                     ans=(ans*temp)%p;
              }
              n>>=1;
              temp=(temp*temp)%p;
       }
       return  ans;
}

int main() {
     int n;
     /*variables to store 1!*2!*...N!, mod p for pF and pS respectively*/
     LL ansF=1,ansS=1; 
     
     /* variable to store Factorial till array_index mod pF and pS respectively*/
     
     LL tempFactF=1,tempFactS=1; 
     LL pF=186583 ;// First Prime
     LL pS=587117 ;// Second Prime
     LL N=pF*pS;
     scanf("%d",&n);
     for(int i=1;i<=n;++i)
     {
          tempFactS=(tempFactS*i)%pS;
          ansS=(ansS*tempFactS)%pS;
          
          tempFactF=(tempFactF*i)%pF;
          ansF=(ansF*tempFactF)%pF;
     }
     LL xF=ModularExponentiaion(N/pF,pF-2,pF);
     LL xS=ModularExponentiaion(N/pS,pS-2,pS);
     
     LL FinalAns=(ansF*((N/pF)*xF)%N + ansS*((N/pS)*xS)%N)%N;
     printf("%lld\n",FinalAns);
     return 0;
}

Chinese Remainder Theorem

Chinese Remainder Theorem (CRT)

In its basic form, the Chinese remainder theorem will determine a number n that, when divided by some given divisors, leaves given remainders.
For example, what is the lowest number n that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2?

Chinese remainder theorem Problem Statement:

Suppose n1, …, nk are positive integers that are pairwise coprime.
Then, for any given sequence of integers a1, …, ak, there exists an integer x solving the following system of simultaneous congruences.

\begin{cases} x \equiv a_1 & \pmod{n_1} \\ \quad \cdots \\ x \equiv a_k &\pmod{n_k} \end{cases}

We will first provide the solution for two variables(i.e k=2) , then give the general solution. We just provide the final result, all the intermediate steps can be found here

Explantion:

Consider the system (for k=2) :

\begin{cases} x \equiv a_1 & \pmod{n_1} \\ x \equiv a_2 & \pmod{n_2} \end{cases}

Now, for such we can now define the value of X as shown below.

x \equiv a_1 n_2 \left [n_2^{-1} \right ]_{n_1} + a_2 n_1 \left [n_1^{-1} \right ]_{n_2}

and it is seen to satisfy both congruences, for example: where ni-1 represents the inverse of ni with respect to the subscript shown.

Inverse can be calculated using the Fermat’s Little Theorem  as (n1n2-2)mod n2, where n2 and n1 care co-prime.

a_1 n_2 \left [n_2^{-1} \right ]_{n_1} + a_2 n_1 \left [n_1^{-1} \right ]_{n_2} \equiv a_1 \times 1 + a_2 \times 0 \times \left [n_1^{-1} \right ]_{n_2} \equiv a_1 \pmod {n_1}

General case

The same type of construction works in the general case of k congruence equations. Let N = n1nk be the product of every modulus then define

x := \left[\sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}\right]_{N}

and this is seen to satisfy the system of congruences by a similar calculation as before.

Algorithm :

  1. Verify that all ni are pairwise co-prime.
  2. Calculate N = n1nk .
  3. Calculate inverse for each N/ n1 with respect to  n1 .
  4. Substitute in the above shown general case equation to obtain the answer.

Example, consider the problem of finding an integer x such that

\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{4} \\ x \equiv 1 \pmod{5} \end{cases}

To find an x that satisfies all three congruences, we apply the above method and get:

x ∈ {11, 71, …}

Which can be expressed as

x \equiv 11 \pmod{60}

Suggested Reading: Modular Exponentiation