Codaline Preliminary Round Questions

4. Recursion

Definition

Recursion is a computer programming technique

involving the use of a procedure, subroutine, function, or algorithm

that calls itself in a step having a termination condition

so that successive repetitions are processed up to the critical step

where the condition is met at which time the rest of each repetition

is processed from the last one called to the first.

Fibonacci series

A series of numbers in which each number (Fibonacci number) is the sum of the two preceding numbers.

1, 1, 2, 3, 5, 8, etc

NOTE: The first term of the series is considered to be 1 (not 0).

Task

fibo(n): This function recursively finds and returns the n^th term of the Fibonacci series.

#Main

· Input two integers, a and b.

· Find the a^th and b^th term of the Fibonacci series (x and y respectively). (a and b cannot be 0 since they are not the indices)

· Multiply the two terms, x and y.

· Print True if the resulting product belongs to the Fibonacci series. Otherwise, print False.

Constraint

a and b are Natural numbers. (1, 2, 3,…..)

NOTE: Your program will not be marked if you do not use the recursive technique.

Input Format

The first line contains a natural number, a.

The next line contains another natural number, b.

Sample Input

2

4

Sample Output

True

Explanation

The second term of the Fibonacci series is 1.

The fourth term of the Fibonacci series is 3.

1 * 3 = 3

3 is a Fibonacci number (it belongs to the Fibonacci series). Therefore, print True.

5. Verify

Task

You are given a polynomial P of a single indeterminate (or variable), x.

You are also given the values of x and k.

Your task is to verify if P(x) = k.

Constraints

All coefficients of polynomial P are integers.

x and k are also integers.

Input Format

The first line contains the space separated values of x and k.

The second line contains the polynomial P.

Output Format

Print True if P(x) = k.

Otherwise, print False.

Sample Input

2 9

x**4 – x**2 * x – 2 + 3

Sample Output

True

Explanation

P(2) = 2⁴ – 2² * 2 – 2 + 3

= 16 – 4 * 2 – 2 + 3

= 16 – 8 – 2 + 3

= 19 – 10

= 9

Hence, the output is True.

8. Series

Task

· You are given q queries in the form of a, b and n.

· For each query, print the series and its sum corresponding to the given a, b, and n values as a single line of n+1 space-separated integers.

The series: (a + 2⁰. b), (a + 2⁰. b + 2¹. b), …, (a + 2⁰. b + 2¹. b + … + 2^n-1. b)

Constraints

· 1 ≤ q ≤ 10

· 0 ≤ a, b ≤ 50

· 1 ≤ n ≤ 11

Input Format

The first line contains an integer, q, denoting the number of queries.

Each line i of the q subsequent lines contains three space-separated integers describing the respective a_i, b_i and n_i values for that query.

Output Format

For each query, print the corresponding series and its sum on a new line.

Each series and its sum must be printed in order as a single line of n+1 space-separated integers.

Sample Input

2

0 1 3

5 3 5

Sample Output

1 3 7 11

8 14 26 50 98 196

Explanation

We have two queries:

1. We use a=0, b=1 and n=3 to produce some series s₀, s₁, s₂, …, s_n-1:

· s₀ = 0 + 2⁰.1 = 1

· s₁ = 0 + 2⁰.1 + 2¹.1 = 3

· s₂ = 0 + 2⁰.1 + 2¹.1 + 2².1 = 7

· sum= s₀ + s₁ + s₂ = 11

2. We use a=5, b=3 and n=5 to produce some series s₀, s₁, s₂, …, s_n-1:

· s₀ = 5 + 2⁰.3 = 8

· s₁ = 5 + 2⁰.3 + 2¹.3 = 14

· s₂ = 5 + 2⁰.3 + 2¹.3 + 2².3 = 26 ……

Once we hit n=5, we print the first five terms and their sum (8 + 14 + 26 + 50 + 98 = 196) as a single line of space-separated integers.

9. Subarray

Task

· You are given an array of n integers,

· Find and print its number of negative subarrays on a new line.

Definitions

· A subarray of an n-element array is an array made from a contiguous block of the original array's elements. For example, if A = [1,2,4], then the subarrays of A are [1], [2], [4], [1, 2], [2, 4] and [1, 2, 4].

[2, 4] will not be a subarray as it is not a contiguous subsection of the original array.

· The sum of an array is the total sum of its elements.

Ø The sum of an array is negative if the sum of all its elements is negative.

Ø The sum of an array is positive if the sum of all its elements is positive.

Constraints

· 1 ≤ n ≤ 20

· -9999≤ a_i ≤ 9999

Input Format

The first line contains an integer, n which is the length of the array .

A = [a₀, a₁, …, a_n-1]

The second line contains n space-separated integers describing each respective element, a_i, in array the A.

Output Format

Print the number of subarrays of A having negative sums.

Sample Input

3

1 -2 -2 6

Sample Output

9

Explanation

There are nine negative subarrays of A = [1, -2, -2, 6]:

[-2] → -2

[1, -2] → 1 + (-2) = -1

[-2, -2] → (-2) + (-2) = -4

[1, -2, -2] → 1 + (-2) + (-2) = -3

10. Student list

Task

· You are given a list of students with the following information for each of them: rollno, First Name, and their percentage.

· Rearrange the list according to their percentage in decreasing order.

· If two or more students have the same percentage, then arrange them according to their first name in alphabetical order.

· If those two (or more) students also have the same first name, then order them in ascending order of their rollno.

Assume that no two students have the same rollno.

NOTE: The comparison of the names must not be case sensitive. For example: Ram is same as RAM while comparing their names

Input Format

The first line of input contains an integer, n representing the total number of students.

The next n lines contain a list of student information in the following structure:

rollno Name Percentage

Constraints

· 2 ≤ n ≤ 50

· 0 ≤ rollno ≤ 50

· 3 ≤ length of name ≤ 25

· 0 ≤ percentage ≤ 100

NOTE: The percentage will contain, at most, 2 digits after the decimal point.

Output Format

Print the first name and roll number (rollno) of each student on separate lines in the order mentioned in the task section.

Sample Input

5

3 Sajna 36.8

34 Arunava 98

20 Sajna 36.8

11 Shaurya 77.5

48 Drishti 89.00

Sample Output

Arunava 34

Drishti 48

Shaurya 11

Sajna 3

Sajna 20

11. Prime

Task

· You are given an integer, n.

· Take n numbers as input.

· Truncate the numbers and convert them to integers.

· After taking the first number of input and converting it to an integer, print it if it is prime. Otherwise, print a blank line.

· Repeat it after the next input too, but this time, print the previous integer too if it was prime. If the previous number was prime but not this number, print only the previous number. If both are not prime, print a blank line again.

· Repeat this for all the inputs.

NOTE: 1 is neither prime nor composite.

Constraints

· 2 ≤ n ≤ 20

· 0.5 ≤ each number ≤ 99.5

Input Format

The first line contains the number of inputs, n to be taken.

Next, there are n lines of input, each containing one number.

Output Format

As mentioned in the task section.

Sample Input1

5

2.98

1.5

3.0

4

5.098

Sample Output1

2

2

2 3

2 3 5

Sample Input2

5

1.56

1.5

3

2.99

5.098

Sample Output2

3

3 2

3 2 5

(In Sample Output2, two blank lines have been printed first and 3 has been printed in the third line)

Sample Input3

4

1.56

1

4.99

15.00

Sample Output3

(In Sample Output3, four blank lines have been printed)

12. Combine

Task

· You are given sentence, S.

· Form a new string, SN by removing all the ‘a’, ‘A’ and spaces from S.

· Print SN.

· Print the sum of the numbers associated (given below) with each character of the new string, SN.

· Numbers associated with each character:

a-z : 1-26

A-Z : 27-52

Special characters : 0

Digits 0-9 : 53-62

Constraints

· 2 ≤ length of S ≤ 25

Input Format

The sentence S.

Output Format

Print SN.

Print the sum as mentioned in Task.

Sample Input

^Hello. This iS MAya1^

Sample Output

^Hello.ThisiSMy1^

332

Explanation

S = “^Hello. This iS MAya1^”

SN = “^Hello.ThisiSMy1^”

Now, sum = 0 + 34 + 5 + 12 + 12 + 15 + 0 + 46 + 8 + 9 + 19 + 9 + 45 + 39 + 25 + 54 + 0 = 332

Since, number associated with special characters (Here, ^ and . ) is 0

number associated with H=34, e=5, l=12, and so on.

number associated with the digit 1 is 54

13. Rotation

Task

· You are given two strings, a and b.

· Print TRUE if they are rotations of each other. Otherwise, print FALSE.

NOTE: A string is said to be a rotation of another string if it has the same length, contains the same characters, and they were rotated around one of the characters. For example, “bcdea” is a rotation of “abcde” but “aebcd” is not a rotation of “abcde”. Anti clockwise rotation and clockwise rotation both must be considered.

Constraints

· 3 ≤ length of a and b≤ 10

Input Format

String a

String b

Output Format

Print TRUE or FALSE.

Sample Input1

Aabd

abdA

Sample Output1

TRUE

Sample Input2

Hello

elloh

Sample Output2

FALSE

Explanation2

FALSE since ‘H’ and ‘h’ are different characters.

Sample Input3

hello

lleho

Sample Output3

TRUE

Explanation3

14. Numbers

Task

· Create a menu driven program to perform the following tasks.

(1)Check if the number, n is an automorphic number.

(2)Check if the number, n is a neon number.

(3)Check if the number, n is a magic number number.

(4)Check if the number, n is a twin prime number.

NOTE: Print TRUE or FALSE.

Definitions

· Automorphic Number: An integer whose square ends with the given integer. For Example: 25 as (25)² = 625, and 76 as (76)² = 5776

· Neon Number: A number where the sum of digits of square of the number is equal to the number.

· Magic Number: A number is said to be a magic number, if the sum of its digits are calculated till a single digit repeatedly by adding the sum of the digits after every addition. If the single digit comes out to be 1,then the number is a magic number

· Palprime Number: a Prime number that is also a Palindromic number. For Example: 11, 101, 181, 191, 313, 727, 797, 919, 929

Constraints

· 10 ≤ n ≤ 99999

· n must be an integer

Input Format

The choice of the user (1, 2, 3 or 4)

The integer, n

Output Format

Print TRUE or FALSE or INVALID INPUT (If the user enters a choice other than 1,2,3,4)

Sample Input1

2

9

Sample Output1

TRUE

Explanation1

Option 2 checks for neon number.

Square of 9 is 9*9 = 81 and sum of the digits of the square (81) is 9

Sample Input2

3

119

Sample Output2

TRUE

Explanation2

Option 2 checks for magic number.

1+1+9=19

1+9=10

1+0=1

Sample Input3

6

Sample Output3

INVALID INPUT

Sample Input4

3

99999

Sample Output4

FALSE

Explanation4

Option 2 checks for magic number.

9+9+9+9+9=45

4+5=9 ≠ 1

15. Sort

Task

· You are given two integers, n and m.

· Input n integers each in a different line.

· Now print the first m integers in ascending order and the remaining integers in descending order. (in a single line)

NOTE: For those whose will code in Python, you are not allowed to use the sort() or sorted() function. If you do, your program will not be marked.

Constraints

· 4 ≤ n ≤ 15

· 0 ≤ m ≤ n

· -100 < The other inputs < 1000

· n, m and all the other inputs must be an integer

Input Format

The integer n

The integer m

Integer 1

Integer 2

Integer 3

.

.

.

Integer n

Output Format

Print the numbers in the required manner (as mentioned in the task section) in a single line separated by single spaces

Sample Input1

7

2

0

-10

6

999

6

79

80

Sample Output1

-10 0 999 80 79 6 6

Explanation1

Number of integers to be inputted: 7

Number of integers to be sorted in ascending order: 2

Number of integers to be sorted in descending order: 7-2 = 5

The integers inputted: 0, -10, 6, 999, 6, 79, 80

First two integers in ascending order: -10, 0

Remaining integers in descending order: 999, 80, 79, 6, 6

Sample Input2

3

3

90

6

7

Sample Output2

6 7 90

Explanation2

Number of integers to be inputted: 3

Number of integers to be sorted in ascending order: 3

Number of integers to be sorted in descending order: 3-3 = 0

The integers inputted: 90, 6, 7

First three integers in ascending order: 6, 7, 90

No remaining integer.

Sample Input3

4

0

66

68

-70

-9

Sample Output3

68 66 -9 -70

Explanation3

Number of integers to be inputted: 4

Number of integers to be sorted in ascending order: 0

Number of integers to be sorted in descending order: 4-0 = 4

The integers inputted: 66, 68, -70, -9

No integer in ascending order

Remaining integers in descending order: 68, 66, -9, -70

Sample Input4

4

5

0

89

8

66

Sample Output4

INVALID INPUT

Explanation4

Invalid since m=5 > n=4

16. ISBN

The International Standard Book Number (ISBN) is a unique numeric book identifier which is printed on every book. The ISBN is based upon a 10-digit code. The ISBN is legal if:

1xdigit1 + 2xdigit2 + 3xdigit3 + 4xdigit4 + 5xdigit5 + 6xdigit6 + 7xdigit7 + 8xdigit8 + 9xdigit9 + 10xdigit10 is divisible by 11.

Task

· You are given a code, c.

· Print YES if c is a legal ISBN code. Otherwise, print NO.

Constraints

· c should be a 10-digit number

Input Format

The code, c.

Output Format

YES or NO

Sample Input1

1401601499

Sample Output1

YES

Explanation1

For an ISBN 1401601499

Sum = 1×1 + 2×4 + 3×0 + 4×1 + 5×6 + 6×0 + 7×1 + 8×4 + 9×9 + 10×9 = 253 which is divisible by 11.

Sample Input2

8765674

Sample Output2

INVALID INPUT

Explanation2

8765674 is not a 10-digit number