LAB WORKBOOK

17CS3554 - COMPETITIVE CODING LAB

B.TECH 3/4 2019-20 ODD SEMESTER

COMPETITIVE CODING LAB – 17CS3554
 LABORATORY WORKBOOK

STUDENT NAME
REG. NO
YEAR
SEMESTER
SECTION
FACULTY
 TABLE OF CONTENTS

Lab Session Concepts to be covered Page

Lab Session 01 Arrays, Strings and Functions Using C 1

Lab Session 02 OOPs concepts (Classes, Objects, constructors, 12

Overloading and Inheritance) Using C++
Lab Session 03 Polymorphism, Templates and Exception Handling 20
Using
Lab Session 04 Collections (Stacks, Queues, linked List) using java 30

Lab Session 05 input streams and output stream Using Java 43

Lab Session 06 Matrix, Hashing and Bit Manipulation Using java 54

Lab Session 07 Binary Trees, Binary search Trees Using java 64

Lab Session 08 Sorting, List, Tuples, Regular Expressions Using 75

Python
Lab Session 09 Puzzles using C/ C++ / Java/ Python 86

Lab Session 10 Case study- 1 (angle on a clock) 95

Lab Session 11 Case study- 2 (Snake and Ladder Problem) 97

 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING::VRSEC
Competitive Coding Lab Evaluation Sheet, Semester-V 2019-20
In-Lab
Sl. Date Experiment Name Pre-Lab Post Lab Viva Voce Total Faculty
Logic Execution Result Analysis
No. (5M)
(10M) (10M) (10M) (5M)
(5M) (5M) (50M) Signature
1.

2.

3.

4.

5.

6.

7.

8.

9.
Lab Session 01 Arrays, Strings and Functions Using C
Date of Session
Time of Session
:
Pre Lab Questions:

1. Can you declare an array without assigning the size of an array?

2. How to find all permutations of String?

3. What is a static function?

4. Differentiate call by value and call by reference?

5. Program Title: String Matching
Given an input string (s) and a pattern (p), implement regular expression matching
with support for '.' and '*'. The ‘.’ matches any single character. The ‘*’ matches Zero
or more of the preceding elements. The matching should cover the entire input string
(not partial).

Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Sample Input:
s = "aa"
p = "a"
Sample Output: false

Pre Requisites: Prepare Creating, accessing strings and Pointers.

In Lab Programs:
1. Program Title: Longest Common in the given array
Problem Description: Given a array of N strings, find the longest common prefix
among all strings present in the array. The first line of the input contains an
integer T which denotes the number of test cases to follow. Each test case contains
an integer N. Next line has space separated N strings. Print the longest common prefix
as a string in the given array. If no such prefix exists print "-1"(without quotes).

Sample Input:
2
4
geeksforgeeks geeks geek geezer
3
apple ape April

Sample Output:
gee
ap
Pre Requisites: Prepare Creating, accessing strings
2. Program Title: Find longest route possible in a Matrix
Problem Description: Given a rectangular path in the form of binary matrix, find the
length of longest possible route from source to destination position of the matrix by
moving to only non-zero adjacent positions i.e route can be formed from positions
having their value as 1. Note there should not be any cycles in the output path.

Pre Requisites: calling functions, Accessing elements row major and column major
ordering from 2-D Matrix
3. Project based program from any online platform
Post Lab Programs:
1. Program Title: Count pairs with given sum
Problem Description Given an array of integers, and a number ‘sum’, find the
number of pairs of integers in the array whose sum is equal to ‘sum’.
Sample Input: arr[] = {1, 5, 7, -1},
sum = 6
Sample Output: 2
Pairs with sum 6 are (1, 5) and (7, -1)
Pre Requisites: Prepare storing, accessing value of Arrays.
2. Program Title: Palindrome Index.
Problem Description: Given a string of lowercase letters in the range ascii[a-z],
determine a character that can be removed to make the string a palindrome. There
may be more than one solution, but any will do. For example, if your string is "bcbc",
you can either remove 'b' at index 0 or 'c' at index 3. If the word is already a
palindrome or there is no solution, return -1. Otherwise, return the index of a
character to remove.
Pre Requisites: Prepare Creating, accessing strings
 Student Signature
Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 02 OOPs concepts (Classes, Objects, constructors,
Overloading and Inheritance) Using C++
Date of Session
Time of Session

Pre lab Questions:

1. What is class and what is object explain it with real life example?

2. Differentiate between class and structure.

3. How to use static variable and static function?

4. Construct a class called Time with three private data members: hour (0-23), minute
(0-59) and second (0-59), with default values of 0.Three private data members: hour
(0-23), minute (0-59) and second (0-59), with default values of 0. A public
constructor Time(), which initializes the data members hour, minute and second with
the values provided by the caller. public getters and setters for private data members:
getHour(), getMinute(), getSecond(), setHour(), setMinute(), and setSecond(). A
public member function setTime() to set the values of hour, minute and second given
by the caller. A public member function print() to print this Time instance in the
format "hh:mm:ss", zero-filled, e.g., 01:30:04.

5. Describe Operator overloading.

6. When do you call copy constructors?

In lab Programs:
Program Description
Kristen is a contender for valedictorian of her high school. She wants to know how many
students (if any) have scored higher than her in the 5 exams given during this semester.
Create a class named student with the following specifications:
 An instance variable named scores to hold a student's 5 exam scores.
 A void input() function that reads 5 integers and saves them to scores. .
 An int calculateTotalScore() function that returns the sum of the student's scores.

Input Format

Most of the input is handled for you by the locked code in the editor.
In the void Student::input() function, you must read 5 scores from stdin and save them to
your scores instance variable.

Constraints

Output Format
In the int Student::calculateTotalScore() function, you must return the student's total
grade (the sum of the values in scores ).The locked code in the editor will determine
how many scores are larger than Kristen's and print that number to the console.
Sample Input

The first line contains , n the number of students in Kristen's class. The n subsequent lines
contain each student's 5 exam grades for this semester.
3
30 40 45 10 10
40 40 40 10 10
50 20 30 10 10
Sample Output
1
Pre Requisites: Prepare OOPS concepts
3. Project based program from any online platform

Accessing Inherited Functions

https://www.hackerrank.com/challenges/accessing-inherited-functions/problem
Post Lab Programs:
Applying Inheritance
Program Description: Create two classes:
The Rectangle class should have two data fields-width and height of int types. The class
should have display()method, to print the width and height of the rectangle separated by
space. The RectangleArea class is derived from Rectangle class, i.e., it is the sub-class of
Rectangle class. The class should have read_input() method, to read the values of width and
height of the rectangle. The RectangleArea class should also overload the display() method
to print the area (width*height) of the rectangle.

Input Format
The first and only line of input contains two space separated integers denoting the width and
height of the rectangle.

Constraints
1 <= width,height <= 10^3

Output Format
The output should consist of exactly two lines:
In the first line, print the width and height of the rectangle separated by space.
In the second line, print the area of the rectangle.
Sample Test Case
Input

5 100

Output

5 100
500
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 03 Polymorphism, Templates and Exception Handling Using
C++.
Date of Session
Time of Session

Pre Lab Questions:

1. How to use templates in C++

2. Where to Use Class Templates in C++

3. Creating a class Numbers which has two generic type variable x and y; Now create
two objects NUM1 and NUM2 which will accept integer and float type data types.

4. Illustrate three parameter passing techniques in c++.

5. Explain about compile time and run time binding in c++.

6. When to use Inline functions?

7. Program Title: program to convert a string of number to integer

Program Description: Write a function to convert a given string into the number it
represents. That is input will be a numeric string that contains only numbers, you need
to convert the string into corresponding integer and return the answer.
Input format: Numeric string (string, Eg. "1234")
Output format: Corresponding integer (int, Eg. 1234)
Sample Input 1: "1231"
Sample Output 1: 1231
Pre Requisites: Prepare Templates
In Lab Programs:

Program Title: FUNNY String.

Program Description: Hari has a problem for you. He will provide you a string consisting of
lowercase letters, uppercase letters and digits and you have to tell if the string is funny or not.

A string is considered to be funny if it contains at least three vowels in uppercase, alphabet x,

y, z in lowercase and only the even digits.

Input Format

The first line of input consist of number of test cases, T

Next T lines consist of the strings.
Constraints
1<= T <=10
1<= |string_length| <=1000
Output Format
For each test case, print "FUNNY" if the string is funny otherwise throw Exception

Sample Test Case

Input

3
Aeixy246
ExIOz8y02
asdxyzERTYUI

Output

NOT FUNNY

FUNNY

NOT FUNNY
Pre Requisites: Prepare Templates, Exception Handling
2. Program Title: Report Card

Program Description: The marks, name and grade of the student will be provided and you
have to create classes and work accordingly.

The Student class will have a read() function which will read the name of the student and
marks of 5 subjects. The Student class will have another function read_grade() to read the
grade of the student. The class Percentage will calculate the percentage up to 2 decimal
points. The class Grade will return the grade obtained by the Student. The class Report will
print the name of the student, marks in the 5 subjects, percentage and the grade.
Input Format
The first line of input consist of the number of test cases, T.
The first line of each test case consist of the name of the student.
The second line of each test case consist of the marks of the 5 subjects space separately.
The third line of each test case consist of the grade obtained.
Constraints
1<= |name| <=50
0<= M1, M2, M3, M4 M5 <=100
grade={A, B, C, D}
Output Format
The name of the student is to be printed in the first line.
The marks obtained in the 5 subjects is to printed in the second line.
The percentage and grade is to be printed in the third line space separately.
Sample Test Case

Input

2
Monti
10 20 30 40 50
C
Roy
30 40 50 60 70
C

Output

Monti
10 20 30 40 50

30.00% C

Roy

30 40 50 60 70

50.00% C

Pre Requisites: Prepare features of C++

Post Lab Programs:
Program Title: Chess Board
Program Description: A chess board is equally divided into 64 identical squares that are
black and white alternately. Each square on the chessboard can be identified by the
coordinates as 'A' to 'H' on the horizontal axis and '1' to '8' on the vertical axis as shown in the
figure. If the square not find the throw the exception.

Pre Requisites: Prepare C++ features

 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 04 Collections (Stacks, Queues, linked List) using java
Date of Session
Time of Session

Pre Lab Questions:

1. What are the main differences between array and collection?

2. What is the difference between Set and Map?

3. Discuss how to implement queue using stack

4. What is Priority Queue?

5. Program Title: Balanced Brackets

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].
Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [,
or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type.
There are three types of matched pairs of brackets: [], {}, and ().
A matching pair of brackets is not balanced if the set of brackets it encloses are not
matched. For example, {[(])} is not balanced because the contents in between { and }
are not balanced. The pair of square brackets encloses a single, unbalanced opening
bracket, (, and the pair of parentheses encloses a single, unbalanced closing square
bracket, ].
By this logic, we say a sequence of brackets is balanced if the following conditions
are met:
  It contains no unmatched brackets.
 The subset of brackets enclosed within the confines of a matched pair of
brackets is also a matched pair of brackets.
Given n strings of brackets, determine whether each sequence of brackets is balanced.
If a string is balanced, return YES. Otherwise, return NO
Input Format
The first line contains a single integer n , the number of strings.
Each of the next n lines contains a single string s,, a sequence of brackets.
Constraints:

Output Format
For each string, return YES or NO.
Sample Input
3
{[()]}
{[(])}
{{[[(())]]}}
Sample Output
YES
NO
YES
Pre Requisites: Prepare stack Operations
In Lab Programs:
1. Program Title: Print the Elements of a Linked List
If you're new to linked lists, this is a great exercise for learning about them. Given a pointer
to the head node of a linked list, print its elements in order, one element per line. If the head
pointer is null (indicating the list is empty), don’t print anything.
Input Format
The first line of input contains n,, the number of elements in the linked list.
The next n, lines contain one element each, which are the elements of the linked list.
Note: Do not read any input from stdin/console. Complete the print Linked List function in
the editor below.
Constraints

Sample Input
2
16
13
Sample Output
16
13
Pre Requisites: Prepare Operations on linked list
2. Program Title: Castle on the Grid
Program Description: You are given a square grid with some cells open (.) and some
blocked (X). Your playing piece can move along any row or column until it reaches the edge
of the grid or a blocked cell. Given a grid, a start and an end position, determine the number
of moves it will take to get to the end position.
For example, you are given a grid with sides n=3 described as follows:
...
.X.
...

Input Format
The first line contains an integer n, the size of the array grid.
Each of the next n lines contains a string of length

.
The last line contains four space-separated integers, startX, startY, goalx, goalY
Sample Input
3
.X.
.X.
...
0002
Sample Output
3
Pre Requisites: Prepare queue operations
3. Project based program from any online platform
Post Lab Programs:
1. Program Title: Steps by Knight [Medium]
Program Description: Given a square chessboard of N x N size, the position of Knight and
position of a target is given.
We need to find out minimum steps a Knight will take to reach the target position.

Input Format
The first line of input contains an integer T denoting the number of test cases. Then T test
cases follow. Each test case contains an integer n denoting the size of the square chessboard.
The next line contains the X-Y coordinates of the knight. The next line contains the X-Y
coordinates of the target.

Constraints
1<=T<=100
1<=N<;=20
1<=knight_pos, targer_pos<=N

Output Format
Print the minimum steps the Knight will take to reach the target position.
Sample Input
2
6
45
11
20
57
15 20
Sample Output
3
9
Pre Requisites: Prepare Queue Operations
2. Program Title: Stamina Game
Program Description: A college in France is organizing a different type of game in which N
players are aligned in a queue. Each player has stamina Si associated with him. At each
minute 4 players from front of the queue are eliminated from the queue and their stamina
decreased by 1 and re-inserted again. If at any point the stamina of player is reduced to zero
then he is removed from the game and not inserted in the queue. Now your task is to print the
stamina of first player in current queue. If anytime Ti < T if number of players in the queue
are less than 4 then then eliminate all the remaining players are re-insert in same manner. If at
time T there are no players left in the game then print -1.

Input Format
First line contain Input N denoting number of players in the game followed by time T at
which position of top player is to be checked.
Second line input contain space separated N integers denoting the stamina of the players in
the queue.
Constraints
1 < N, T < 1000
1 <= Ai <= 10000

Output Format
Output single integer specifying the stamina of first player in current queue.
Sample Input
77
53
49758
Pre Requisites: Prepare Queue Operations
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 05 input streams and output stream Using Java
Date of Session
Time of Session

Pre Lab Questions:

1. What are the different file access modes?

2. Differentiate between input output stream with example.

3. Differentiate File reader and writer functions.

In Lab Programs:
1. Program Title: count the frequency of each word in file
Problem Description: Find the frequency of each word given in the input file and
display the count of each word.
Pre Requisites: Prepare Functions to read and write operations on a file.
2. Program Title: Base 7
Problem Description: Given an integer, return its base 7 string representations to an
output file.
Pre Requisites: Reading and writing data from various input output stream in java
3. Project based program from any online platform
Post Lab Programs:

1. Program Title: Minimum Time required using file input output streams

Problem Description: You are planning production for an order. You have a number of
machines that each have a fixed number of days to produce an item. Given that all the
machines operate simultaneously, determine the minimum number of days to produce the
required order.
For example, you have to produce items. You have three machines that take days to produce
an item. The following is a schedule of items produced:
Sample Input
25
23

Sample Output
6

Explanation

In 6 days can machine 0 produce 3 items and machine 1 can produce 3 items. This totals up
to 5 .
Pre Requisites: Reading and writing data form various input output stream in java
2. Program Title : Boats to Save People
Program Description: The i-th person has weight people[i], and each boat can carry a
maximum weight of limit. Each boat carries at most 2 people at the same time, provided the
sum of the weight of those people is at most limits. Return the minimum number of boats to
carry every given person. (It is guaranteed each person can be carried by a boat.)

Input: people = [1,2], limit = 3

Output: 1
Explanation: 1 boat (1, 2)
Pre Requisites: Reading and writing data from various input output stream in java
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 06 Matrix, Hashing and Bit Manipulation Using java
Date of Session
Time of Session

Pre Lab Questions:

1. What can be the techniques to avoid collision with example?

2. Where does the number 14 get inserted in the following table?

index Key
0
1 79
2
3
4 69
5 98
6
7 72
8
9
10
11 50
12
3. Applications of hashing?

4. Program Title: Multiply 16 bit integer using 8-bit multiplier

Problem Description: Given two positive values stored in 32 bit integer variables,
find the product using the 8-bit multiply operator that takes two 8-bit numbers and
returns a 16-bit value

You are given a matrix with M rows and N columns. Print count of all possible paths
from top left to bottom right of a m*n matrix

Sample Input
2
3
123
456

Output
3
Pre Requisites: Prepare Bit Manipulation Operations
In Lab Programs:

1. Program Title: Largest square house

Problem Description: Given an N X M matrix where some position is free and some
have trees in them. You can build a house on any group of free positions that form a
square (including a single position). You need to print the largest house you can build
given these requirements. (Free positions are represented by 0 while trees are represented
by 1).

Sample Input
4
5
11100
11100
01010
00111

Sample Output
2$2
2. Program Title: Reverse bits of a given 32 bits unsigned integer.
Problem Description: For Example The input binary string
00000010100101000001111010011100 represents the unsigned integer 43261596, so
return 964176192 which its binary representation is
00111001011110000010100101000000.

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Pre Requisites: Prepare reading and storing binary numbers.
3. Project based program from any online platform
Post Lab Programs:
1. Program Title: H-index
Problem Description:
Given an array of citations (each citation is a non-negative integer) of a researcher, write a
function to compute the researcher's h-index. According to the definition of h-index on
Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and
the other N − h papers have no more than h citations each."
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3
citations each and the remaining two with no more than 3 citations each, her h-index is 3.
Pre Requisites: Prepare different hashing Techniques

2. Program Title: Top K Frequent Elements

Problem Description: Given a non-empty array of integers, return the k most frequent
elements.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Pre Requisites: Prepare different hashing Techniques
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 07 Binary Trees, Binary search Trees Using java
Date of Session
Time of Session

Pre Lab Questions:

1. What are the types of Binary tree?

2. How to add a Node in Binary Tree, Binary Search Tree?

3. Check whether following Binary Trees are foldable or not.

4. Program Title: Find a Triplet with given sum in a BST
Problem Description: Given a Binary search tree, find a triplet with given sum present in it.
For example, consider a below BST. if given sum is 20,the triplet is(-40,10,50)

10

-15 20

- 3 15 50
Sample Output:
Triplet found: (-40,10,50)
Pre Requisites: creation of BST and retrieving its values.
In Lab Programs:

1. Program Title: Print the first shortest root to leaf path in a Binary Tree
Program Description: Given a Binary Tree with distinct values, the task is to print the first
smallest root to leaf path. We basically need to print the leftmost root to leaf path that has the
minimum number of nodes.
Input: Output:1 3 5
1
/ \
2 3
/ /\
4 5 7
/\ \
10 11 8
Input: Output: 10
11
/ \
8 10
/ / \
5 9 8
/\
4 6
2. Program Title: Convert a Binary tree into a Doubly Linked list in Spiral order
Problem Description: Given a binary tree, Convert it into a Doubly linked list in the spiral
order, the conversion should be done in such a way that the left child pointer of a binary
tree node should act as a previous pointer for doubly linked list node and right child
pointer should act as a next pointer for doubly linked list node.

Sample output: 1->2->3->7->6->5->4->NULL

Pre Requisites: binary tree, linked list creation, binary tree values retrieving process.
3. Project based program from any online platform
Post Lab Programs:
1. Program Title: Find Kth smallest and largest element in BST
Problem Description: Given a BST and a positive number K, Find Kth smallest and largest
element in BST.
For example, consider below BST if k=2,then find Kth smallest is 10 and Kth largest is
20 in the given tree.

Output: 10 20
Pre Requisites: creation of BST and retrieving its values.
2. Program Title: Sum and Product of minimum and maximum element of Binary Search Tree.
Problem Description: Given a Binary Search Tree. The task is to find the sum and product
of maximum and minimum value of tree

OUTPUT:
Sum and product of maximum and minimum value of tree is 26 and 88.
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 08 Sorting, List, Tuples, Regular Expressions Using Python
Date of Session
Time of Session

Pre Lab Questions:

1. Define the terms list, Sets, Tuples, Dictionary?

2. What is the usage of Regular Expressions?

3. Differentiate between list and tuple with example?

1. Program Title: Delete And Earn
Problem Description: Given an array nums of integers, you can perform operations on
the array. In each operation, you pick any nums[i] and delete it to earn nums[i] points.
After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.
You start with 0 points. Return the maximum number of points you can earn by applying
such operations.

Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
Pre Requisites: Prepare various operations on List and tuples.
In Lab Programs:
1. Program Title: Minimum Window Substring.
Problem Description: Given a string S and a string T, find the minimum window in S
which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
 If there is no such window in S that covers all characters in T, return the empty
string "".
 If there is such window, you are guaranteed that there will always be only one unique
minimum window in S.
Pre Requisites: Validating string using regular expressions.
2. Program Title: Interleaving String
Program Description: Given s1, s2, s3, find whether s3 is formed by the interleaving
of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Pre Requisites: Validating string using regular expressions.
3. Project based program from any online platform
Post Lab Programs:
1. Program Title: Word Break
Program Description: Given a non-empty string s and a dictionary wordDict containing a
list of non-empty words, determine if s can be segmented into a space-separated sequence of
one or more dictionary words.
Note:
 The same word in the dictionary may be reused multiple times in the segmentation.
 You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Pre Requisites: Validating string using regular expressions.
2. Program Title: Replace all occurrences of 0 that are not surrounded by 1 in a binary Matrix
Program Description: Given a MXN binary matrix, replace all occurrence of 0 by 1 which are not
completely surrounded by 1.
Sample input:

Sample output:

Prerequisite: Prepare various operations on List and tuples.

 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 09 Puzzles using c/ c++ / java/ python
Date of Session
Time of Session

Pre Lab Programs:

1. Program Title: Pokemon
Program Description:
In Pallet town of Kanto region, there lived a young boy named Ash Ketchum. Ash loves
Pokemon and has a dream of becoming a Pokemon Master. He is about to start his
Pokemon journey so he reaches to Professor Oak to get his first starter Pokemon. Before
giving Ash his starter Pokemon, Professor Oak needs to check whether he is capable of
raising a Pokemon or not. So, the professor gave him a task to test his knowledge about
Pokemon. The task is as follows:

Each Pokemon can be represented by a unique ID number and its strength is equivalent to
the total number of factors (including 1 and number itself) of its ID number. In a
Pokemon battle, a Pokemon with higher strength will always win a battle against a
Pokemon with lower strength. Let the total number of Pokemon's in Kanto region
be N(their ID ranging from 1 to N). Given a Pokemon ID number K. Find the total
number of Pokemon, the given Pokemon can certainly beat.

Input Format:
First line of input contains space separated T and N, where T denotes the total number of
test cases.
Each test case contains an integer K.

Output Format:
For every test case, output the correct answer in new line.
Constraints:
1 ≤ T ≤ 105
1 ≤ N ≤ 106
1≤K≤N

Sample Input
2 8
3
4
Sample Output
1
5
In Lab Programs:
1. Program Title: Number of wins for each player in a series of Rock-Paper-Scissor game

Two players are playing a series of games of Rock–paper–scissors. There are a total
of K games played. Player 1 has a sequence of moves denoted by string A and similarly
player 2 has string B. If any player reaches the end of their string, they move back to the start
of the string. The task is to count the number of games won by each of the player when
exactly K games are being played.

Input: k = 4, a = “SR”, b = “R”

Output: 0 2
Game 1: Player1 = S, Player2 = R, Winner = Player2
Game 2: Player1 = R, Player2 = R, Winner = Draw
Game 3: Player1 = S, Player2 = R, Winner = Player2
Game 4: Player1 = R, Player2 = R, Winner = Draw

Input: k = 3, a = “S”, b = “SSS”

Output: 0 0
All the games are draws.

Pre Requisites: Prepare Creating, accessing strings

Post Lab Programs:
1. Program Title: Buy minimum items without change and given coins
Problem Description: You have an unlimited number of 10-rupee coins and exactly one coin
of r rupee and you need to buy minimum items each of cost k such that you do not ask for
change.
Input: k = 15, r = 2
Output: 2
You should buy two cables and pay 2*15=30 rupees. It is obvious that you can pay this sum
without any change.

Input: k = 237, r = 7
Output:1
It is enough for you to buy one cable.

Pre Requisites: Arithmetic operators

2. Program Title: Time taken by two persons to meet on a circular track

Problem Description: Given integers L, S1 and S2 where L is the length of a circular track
in meters, S1and S2 are the speeds of two persons in kilometers/hour moving in the same
direction on the given track starting from the same starting point. The task is to find the
following:
 The time after which they will meet for the first time.
 The time at which there are going to meet at the starting point.

Input: L = 30, S1 = 5, S2 = 2

Output: Met first time after 10 hrs

Met at starting point after 30 hrs

Input: L = 10, S1 = 1, S2 = 2

Output: Met first time after 10 hrs

Met at starting point after 10 hrs
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 10 Case study- 1
Date of Session
Time of Session

Program Title: Calculate the angle on a clock

This problem asks you to determine the angle between the two hands on a clock. For
example, if the minute hand is on the 3 and the hour hand is on the 12, then this forms a 90
degree angle. If the hour hand is slightly past the 2 and the minute hand is on the 4, then the
angle formed between the hands is 50 degrees (image below for reference [Clock angle
problem on Wikipedia: http://bit.ly/2dxFmmt]).

We will solve this problem by first calculating the angles for the hour hand and minute hand
separately. The minute hand is the easiest and that is simply:
Minute hand angle = 6 * minutes because there are 360 degrees total on the clock and there
are a total of 60 minutes, so 360 / 60 = 6 degrees per minute. The hour hand is a bit trickier
because it moves slightly every time the minute hand moves. Therefore, to calculate the angle
of the hour hand we need to take into account how much the minute hand has moved.
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation
Lab Session 11 Case study-2 Snake and Ladder Problem
Date of Session
Time of Session

Program title: Snake and Ladder Problem

Problem Description: Given a snake and ladder board, find the minimum number of dice
throws required to reach the destination or last cell from source or 1st cell. Basically, the
player has total control over outcome of dice throw and wants to find out minimum number
of throws required to reach last cell.

If the player reaches a cell which is base of a ladder, the player has to climb up that ladder
and if reaches a cell is mouth of the snake, has to go down to the tail of snake without a dice
throw.

For example, consider the board shown, the minimum number of dice throws required to
reach cell 30 from cell 1 is 3.
Following are the steps:
a) First throw two on dice to reach cell number 3 and then ladder to reach 22
b) Then throw 6 to reach 28.
c) Finally through 2 to reach 30.
There can be other solutions as well like (2, 2, 6), (2, 4, 4), (2, 3, 5).. etc.
The idea is to consider the given snake and ladder board as a directed graph with number of
vertices equal to the number of cells in the board. The problem reduces to finding the shortest
path in a graph. Every vertex of the graph has an edge to next six vertices if next 6 vertices do
not have a snake or ladder. If any of the next six vertices has a snake or ladder, then the edge
from current vertex goes to the top of the ladder or tail of the snake. Since all edges are of
equal weight, we can efficiently find shortest path using Breadth First Search of the graph.

Following is the implementation of the above idea. The input is represented by two things,
first is ‘N’ which is number of cells in the given board, second is an array ‘move[0…N-1]’ of
size N. An entry move[i] is -1 if there is no snake and no ladder from i, otherwise move[i]
contains index of destination cell for the snake or the ladder at i.
 Student Signature

Comments of the
Evaluator(if any)
Marks Secured
Name of
Evaluator
Signature of the
Evaluator
Date of
Evaluation