Algorithms | Ajinkya Wavare

Utopian Tree

Problem Statement

The Utopian Tree goes through 2 cycles of growth every year. The first growth cycle occurs during the spring, when it doubles in height. The second growth cycle occurs during the summer, when its height increases by 1 meter.

Now, a new Utopian Tree sapling is planted at the onset of spring. Its height is 1 meter. Can you find the height of the tree after N growth cycles?

Input Format

The first line contains an integer, T, the number of test cases.
T lines follow; each line contains an integer, N, that denotes the number of cycles for that test case.

Constraints
1≤T≤10
0≤N≤60

Output Format

For each test case, print the height of the Utopian Tree after N cycles. Each line thus has to contain a single integer, only.

Sample Input

Sample Output

1
2
7

Explanation

There are 3 test cases.

In the first case (N=0), the initial height (1) of the tree remains unchanged.

In the second case (when N = 1, i.e. after the 1^st cycle), the tree doubles its height as it’s planted at the onset of spring.

In the third case (N=4), the tree first doubles its height (2), then grows a meter (3), then doubles again (6), before growing another meter; at the end of the 4^th cycle, its height is 7 meters.

Solution

  
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args)throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int i,j,yr;
        int t = Integer.parseInt(br.readLine());
        while(t!=0){
            yr=1;
            int n=  Integer.parseInt(br.readLine());
            for(i=1;i<=n;i++){
                if(i%2==0)
                    yr++;
                else yr= yr *2;
            }
            System.out.println(yr);
            t--;
        }

    }
}

Sherlock and The Beast

Problem Statement

Sherlock Holmes is getting paranoid about Professor Moriarty, his arch-enemy. All his efforts to subdue Moriarty have been in vain. These days Sherlock is working on a problem with Dr. Watson. Watson mentioned that the CIA has been facing weird problems with their supercomputer, ‘The Beast’, recently.

This afternoon, Sherlock received a note from Moriarty, saying that he has infected ‘The Beast’ with a virus. Moreover, the note had the number N printed on it. After doing some calculations, Sherlock figured out that the key to remove the virus is the largest Decent Number having N digits.

A Decent Number has the following properties:

3, 5, or both as its digits. No other digit is allowed.
Number of times 3 appears is divisible by 5.
Number of times 5 appears is divisible by 3.

Meanwhile, the counter to the destruction of ‘The Beast’ is running very fast. Can you save ‘The Beast’, and find the key before Sherlock?

Input Format
The 1^st line will contain an integer T, the number of test cases. This is followed by T lines, each containing an integer N. i.e. the number of digits in the number.

Output Format
Largest Decent Number having N digits. If no such number exists, tell Sherlock that he is wrong and print −1.

Constraints
1≤T≤20
1≤N≤100000

Sample Input

Sample Output

-1
555
33333
55555533333

Explanation
For N=1, there is no such number.
For N=3, 555 is the only possible number.
For N=5, 33333 is the only possible number.
For N=11, 55555533333 and all permutations of these digits are valid numbers; among them, the given number is the largest one.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n;
    cin>>t;
    while(t--)
    {
       cin>>n;
       string ks;
       for(int j=n;j>=0;j--)
       {
           if(j%3==0 && (n-j)%5==0)
           {
            ks="";
            for(int i=0;i<j;i++)
                ks+='5';
            for(int i=0;i<n-j;i++)
                ks+='3';
            break;   
            }
       }
       if(ks=="")
               cout<<-1<<endl;
       else 
               cout<<ks<<endl;
    }
    return 0;
}

Angry Professor

Problem Statement

The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are fewer than K students present after the class starts.

Given the arrival time of each student, your task is to find out if the class gets cancelled or not.

Input Format

The first line of the input contains T, the number of test cases. Each test case contains two lines.
The first line of each test case contains two space-separated integers, N and K.
The next line contains N space-separated integers, a1,a2,…,aN, representing the arrival time of each student.

If the arrival time of a given student is a non-positive integer (ai≤0), then the student enters before the class starts. If the arrival time of a given student is a positive integer (ai>0), the student enters after the class has started.

Output Format

For each testcase, print “YES” (without quotes) if the class gets cancelled and “NO” (without quotes) otherwise.

Constraints

1≤T≤10
1≤N≤1000
1≤K≤N
−100≤ai≤100,where i∈[1,N]

Note
If a student enters the class exactly when it starts (ai=0), the student is considered to have entered before the class has started.

Sample Input

Sample Output

YES
NO

Explanation

For the first test case, K=3, i.e., the professor wants at least 3 students to be in class but there are only 2 who have arrived on time (−3 and −1), hence the class gets cancelled.

For the second test case, K=2, i.e, the professor wants at least 2 students to be in class and there are 2 who have arrived on time (0 and −1), hence the class does not get cancelled.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t,n,k,i,count;
    cin>>t;
    while(t--){
        count=0;
        cin>>n>>k;
        for(i = 0; i < n; i++)
            { 
            int temp;
            cin>>temp;
            if(temp <= 0)
                count++;
        }
        if(count >= k)
            cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

Extra long factorials

Problem Statement

You are given an integer N. Print the factorial of this number.

N! = N \times (N - 1) \times (N - 2) \times \dots \times 3 \times 2 \times 1

Note: Factorials of N>20 can’t be stored even in a 64−bit long long variable. Big integers must be used for such calculations. Languages like Java, Python, Ruby etc. can handle big integers but we need to write additional code in C/C++ to handle such large values.

We recommend solving this challenge using BigIntegers.

Input Format
Input consists of a single integer N.

Constraints
1≤N≤100

Output Format
Output the factorial of N.

Sample Input

Sample Output

15511210043330985984000000

Solution

  
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args)  throws Exception{
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        //BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        //int n = Integer.parseInt(br.read());
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        BigInteger ans = BigInteger.ONE;
        for (int i=1;i<=n;i++)
            {
            ans = ans.multiply(new BigInteger(String.valueOf(i))); 
        }
        System.out.println(ans);
    }
}

Library Fine

Problem Statement

The Head Librarian at a library wants you to make a program that calculates the fine for returning the book after the return date. You are given the actual and the expected return dates. Calculate the fine as follows:

If the book is returned on or before the expected return date, no fine will be charged, in other words fine is 0.
If the book is returned in the same month as the expected return date, Fine = 15 Hackos × Number of late days
If the book is not returned in the same month but in the same year as the expected return date, Fine = 500 Hackos × Number of late months
If the book is not returned in the same year, the fine is fixed at 10000 Hackos.

Input Format

You are given the actual and the expected return dates in D M Y format respectively. There are two lines of input. The first line contains the D M Y values for the actual return date and the next line contains the D M Y values for the expected return date.

Constraints
1≤D≤31
1≤M≤12
1≤Y≤3000

Output Format

Output a single value equal to the fine.

Sample Input

9 6 2015
6 6 2015

Sample Output

Explanation

Since the actual date is 3 days later than expected, fine is calculated as 15×3=45 Hackos.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int d1,d2,m1,m2,y1,y2;
    cin>>d2>>m2>>y2;
    cin>>d1>>m1>>y1;
    if(y2>y1)
    {
        cout<<10000;
        exit;
    }
    else if(y1==y2 && m2>m1)
        {
        cout<<(m2-m1)*500;
    }
    else if (y1==y2 && m2==m1 && d2>d1)
        cout<<(d2-d1)*15;
    else cout<<0;
    return 0;
}

Time Conversion

Problem Statement

You are given time in AM/PM format. Convert this into a 24 hour format.

Note Midnight is 12:00:00AM or 00:00:00 and 12 Noon is 12:00:00PM.

Input Format

Input consists of time in the AM/PM format i.e. hh:mm:ssAM or hh:mm:ssPM
where
01≤hh≤12
00≤mm≤59
00≤ss≤59

Output Format

You need to print the time in 24 hour format i.e. hh:mm:ss
where
00≤hh≤23
00≤mm≤59
00≤ss≤59

Sample Input

07:05:45PM

Sample Output

19:05:45

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int h,m,s;
    char c;
    scanf("%d:%d:%d%c",&h,&m,&s,&c);
    if(c=='P')
        if(h==12)
            cout<<12;
        else cout<<h+12;
    else if(h<10)
            cout<<"0"<<h;
    else if(h==12)
        cout<<"00";
    else cout<<h;    
    if(m<10)
        cout<<":0"<<m;
    else cout<<":"<<m;
    if(s<10)
        cout<<":0"<<s;
    else cout<<":"<<s;    
    
    return 0;
}

Staircase

Problem Statement

Your teacher has given you the task to draw the structure of a staircase. Being an expert programmer, you decided to make a program for the same. You are given the height of the staircase. You need to print a staircase as shown in the example.

Input Format

You are given an integer N depicting the height of the staircase.

Constraints
1≤N≤100

Output Format

Draw a staircase of height N in the format given below.

For example:

     #
    ##
   ###
  ####
 #####
######

Staircase of height 6, note that last line has 0 spaces before it.

Sample Input

Sample Output

     #
    ##
   ###
  ####
 #####
######

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {    
        for(j=i;j0;j--)
            cout<<"#"; 
        cout<<endl;        
            
    }        
    return 0;
}

Plus Minus

Problem Statement

You’re given an array containing integer values. You need to print the fraction of count of positive numbers, negative numbers and zeroes to the total numbers. Print the value of the fractions correct to 3 decimal places.

Input Format

First line contains N, which is the size of the array.
Next line contains N integers A1,A2,A3,⋯,AN, separated by space.

Constraints
1≤N≤100
−100≤Ai≤100

Output Format

Output three values on different lines equal to the fraction of count of positive numbers, negative numbers and zeroes to the total numbers respectively correct to 3 decimal places.

Sample Input

6
-4 3 -9 0 4 1

Sample Output

0.500
0.333
0.167

Explanation

There are 3 positive numbers, 2 negative numbers and 1 zero in the array.
Fraction of the positive numbers, negative numbers and zeroes are 36=0.500, 26=0.333 and 16=0.167 respectively.

Note This challenge introduces precision problems. You can even print output to 4 decimal places and above but only the difference at 3rd decimal digit is noted. That is the reason you’ll notice testcases have much higher precision (more decimal places) than required.
Answers with absolute error upto 10−4 will be accepted.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int a;
    float n,c1,c2,c3;
    cin>>n;
    for(int i=0;i>a;
       if(a>0)    
            ++c1;
       else if (a==0)
           ++c2;
       else ++c3;    
    }
    cout<<c1/n<<endl;
    cout<<c3/n<<endl;
    cout<<c2/n<<endl;
    return 0;
}

Diagonal Difference

Problem Statement

You are given a square matrix of size N×N. Calculate the absolute difference of the sums across the two main diagonals.

Input Format

The first line contains a single integer N. The next N lines contain N integers (each) describing the matrix.

Constraints
1≤N≤100
−100≤A[i]≤100

Output Format

Output a single integer equal to the absolute difference in the sums across the diagonals.

Sample Input

Sample Output

Explanation

The first diagonal of the matrix is:

11
    5
        -12

Sum across the first diagonal = 11+5-12= 4

The second diagonal of the matrix is:

        4
    5
10

Sum across the second diagonal = 4+5+10 = 19
Difference: |4-19| =15

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int a[100][100],sum1=0,sum2=0,n,i,j;
    cin>>n;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cin>>a[i][j];
    for(i=0;i<n;i++)
    {
        sum1+=a[i][i];
        sum2+=a[i][n-i-1];
    }
    cout<<abs(sum1-sum2);    
    return 0;
}

A Very Big Sum

Problem Statement

You are given an array of integers of size N. You need to print the sum of the elements of the array.

Note: The range of the 32-bit integer is −231 to 231−1 or [−2147483648,2147483647]. When we add several integer values, the resulting sum might exceed this range. You might need to use long long int in C/C++ or long data type in Java to store such sums.

Input Format

The first line of the input consists of an integer N. The next line contains N space-separated integers describing the array.

Constraints
1≤N≤10
0≤A[i]≤1010

Output Format

Output a single value equal to the sum of the elements of the array.

Sample Input

5
1000000001 1000000002 1000000003 1000000004 1000000005

Sample Output

5000000015

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    long a[10],sum=0;
    int t;
    cin>>t;
    while(t--){
        cin>>a[t];
        sum+=a[t];
    }
    cout<<sum;
    return 0;
}