TCS Advance Coding Questions

TCS Advance Coding Questions with Solutions

TCS has announced the hiring for 2024 passouts. Through this new hiring pattern you can get placed in Ninja or Digital depending upon your performance in the recruitement test. TCS has an advanced coding section in this year hiring pattern, that will help you in clearing the role for Digital Profile.

Here, in this article you can practice previous year sample based coding questions, for TCS Advanced Coding Round.

Prime Factors of a Number In C++

Lets Prepare Better Faster

Question 1

Problem Statement-:

Find the minimum number of coins required to form any value between 1 to N,both inclusive.Cumulative value of coins should not exceed N. Coin denominations are 1 Rupee, 2 Rupee and 5 Rupee.Let’s Understand the problem using the following example. Consider the value of N is 13, then the minimum number of coins required to formulate any value between 1 and 13, is 6. One 5 Rupee, three 2 Rupee and two 1 Rupee coins are required to realize any value between 1 and 13. Hence this is the answer. However, if one takes two 5 Rupee coins, one 2 rupee coin and two 1 rupee coin, then too all values between 1 and 13 are achieved. But since the cumulative value of all coins equals 14, i.e., exceeds 13, this is not the answer.



             Input Format:

 

  • A single integer value.

Output Format:

  • Four space separated integer values.
  • 1st – Total number of coins.
  • 2nd – number of 5 Rupee coins.
  • 3rd – number of 2 Rupee coins.
  • 4th – number of 1 Rupee coins.

Constraints:

  • 0 < n < 1000

Refer the sample output for formatting

Sample Input

    13

Sample Output

   6 1 3 2

Explanation

  • The minimum number of coins required is 6 with in it:
  • minimum number of 5 Rupee coins = 1
  • minimum number of 2 Rupee coins = 3
  • minimum number of 1 Rupee coins = 2
  • Using these coins, we can form any value with in the given value and itself, like below:
  • Here the given value is 13
  • For 1 = one 1 Rupee coin
  • For 2 = one 2 Rupee coin
  • For 3 = one 1 Rupee coin and one 2 Rupee coins
  • For 4 = two 2 Rupee coins
  • For 5 = one 5 Rupee coin
  • For 6 = one 5 Rupee and one 1 Rupee coins
  • For 7 = one 5 Rupee and one 2 Rupee coins
  • For 8 = one 5 Rupee, one 2 Rupee and one 1 Rupee coins
  • For 9 = one 5 Rupee and two 2 Rupee coins
  • For 10 = one 5 Rupee, two 2 Rupee and one 1 Rupee coins
  • For 11 = one 5 Rupee, two 2 Rupee and two 1 Rupee coins
  • For 12 = one 5 Rupee, three 2 Rupee and one 1 Rupee coins
  • For 13 = one 5 Rupee, three 2 Rupee and two 1 Rupee coins

 

Question 2

Problem Statement-:

The problem solvers have found a new Island for coding and named it as Philaland. These smart people were given a task to make purchase of items at the Island easier by distributing various coins with different values. Manish has come up with a solution that if we make coin categories starting from $1 till the maximum price of the item present on Island, then we can purchase any item easily. He added the following example to prove his point.

Let’s suppose the maximum price of an item is 5$ then we can make coins of {$1, $2, $3, $4, $5}to purchase any item ranging from $1 till $5.

Now Manisha, being a keen observer, suggested that we could actually minimize the number of coins required and gave the following distribution {$1, $2, $3}. According to him any item can be purchased one time ranging from $1 to $5. Everyone was impressed with both of them.Your task is to help Manisha come up with a minimum number of denominations for any arbitrary max price in Philaland.

Input Format

  • First line contains an integer T denoting the number of test cases.
  • Next T lines contain an integer N denoting the maximum price of the item present Philaland.

Output Format

  • For each test case print a single line denoting the minimum number of denominations of coins required.

Constraints

  • 1<=T<=100
  • 1<=N<=5000

Refer the Sample Output Formatting

Sample Input:

2

10

5

Sample Output:

4

3

Explanation:

For test case 1, N=10.

According to Manish {$1, $2, $3,… $10} must be distributed.

But as per Manisha only {$1, $2, $3, $4} coins are enough to purchase any item ranging from $1 to $10. Hence the minimum is 4. Likewise denominations could also be {$1, $2, $3, $5}. Hence the answer is still 4.

For test case 2, N=5.

According to Manish {$1, $2, $3, $4, $5} must be distributed.

But as per Manisha only {$1, $2, $3} coins are enough to purchase any item ranging from $1 to $5. Hence minimum is 3. Likewise denominations could also be {$1, $2, $4}. Hence the answer is still 3.

Question 3

Problem Statement-:

Given a number ‘N’,find all possible divisors and print them in increasing order.

Input Format:

  • The first line of input contains an integer ‘N’ denoting the number.

Output Format:

  • Print a line containing all the divisors in increasing order separated by space.

Constraints:

  • 1 <= N <= 10^8

Refer the sample output for formatting

Sample Input:

10

Sample Output:

1 2 5 10

Question 4

Problem Statement:-

In a Conference ,attendees are invited for dinner after the conference. The Co-ordinator,Sagar arranged around round tables for dinner and wanted to have an impactful seating experience for the attendees. Before finalising the seating arrangement, he wants to analyse all the possible arrangements.

These are R round tables and N attendees.In case where N is an exact multiple of R, the number of attendees must be exactly N/R. 

If N is not an exact multiple of R, then the distribution of attendees must be as equal as possible.Please refer to the example section before for better understanding.

 

For example, R = 2 and N = 3

All possible seating arrangements are

(1,2) & (3)

(1,3) & (2)

(2,3) & (1)

Attendees are numbered from 1 to N.

Constraints:

  • 0 <= R <= 10(Integer)
  • 0 < N <= 20 (Integer)

Input Format:

  • The first line contains T denoting the number of test cases.
  • Each test case contains two space separated integers R and N, Where R denotes the number of
  • round tables and N denotes the number of attendees.

Output Format:

  • Single Integer S denotes the number of possible unique arrangements.

Sample Input:

Input:

1

2 5

Output:

10

Explanation:

R = 2, N = 5

(1,2,3) & (4,5)

(1,2,4) & (3,5)

(1,2,5) & (3,4)

(1,3,4) & (2,5)

(1,3,5) & (2,4)

(1,4,5) & (2,3)

(2,3,4) & (1,5)

(2,3,5) & (1,4)

(2,4,5) & (1,3)

(3,4,5) & (1,2)

Arrangements like

(1,2,3) & (4,5)

(2,1,3) & (4,5)

(2,3,1) & (4,5) etc.

But as it is a round table,all the above arrangements are the same.

Question 5

Problem Statement:-

Compute the nearest larger number by interchanging its digits updated.Given 2 numbers a and b find the smallest number greater than b by interchanging the digits of a and if not possible print -1.

Constraints:

  • 1 <= a,b <= 10000000

Input Format:

  • 2 numbers a and b, separated by space.

Output Format:

  • A single number greater than b.
  • If not possible, print -1

Example 1:

Input:

459 500

Output:

549

Example 2:

Input:

645757 457765

Output:

465577

Question 6

Problem Statement:-

In this Even-Odd problem – We are given a range [low, high] (both inclusive), and an integer K such that we have to select K numbers from the range (a number can be chosen multiple times) such that the sum of those K numbers is even.

Calculate the number of all such permutations.

As this number can be large, print it modulo (1e9 +7).

Constraints

0 <= low <= high <= 10^9

K <= 10^6.

Input

First line contains two space separated integers denoting low and high respectively

Second line contains a single integer K.

Output

Print a single integer denoting the number of all such permutations

Time Limit

1

Examples

Example 1

Input

4 5

3

Output

4

Explanation

There are 4 valid permutations viz. {4, 4, 4}, {4, 5, 5}, {5, 4, 5} and {5, 5, 4} which sum up to an even number.

Example 2

Input

1 10

2

Output

50

Explanation

There are 50 valid permutations viz. {1,1}, {1, 3},.. {1, 9} {2,2}, {2, 4},… {2, 10} . . . {10, 2}, {10, 4},… {10, 10}. These 50 permutations, each sum up to an even number.

Question 7

Problem Statement:- 

Three characters { #, *, . } represents a constellation of stars and galaxies in space. Each galaxy is demarcated by # characters. There can be one or many stars in a given galaxy. Stars can only be in the shape of vowels { A, E, I, O, U }. A collection of * in the shape of the vowels is a star. A star is contained in a 3×3 block. Stars cannot be overlapping. The dot(.) character denotes empty space.

Given 3xN matrix comprising of { #, *, . } character, find the galaxy and stars within them.

Note: Please pay attention to how vowel A is denoted in a 3×3 block in the examples section below.

Constraints

3 <= N <= 10^5

Input

Input consists of a single integer N denoting the number of columns.

Output

The output contains vowels (stars) in order of their occurrence within the given galaxy. The galaxy itself is represented by the # character.

Example 1

Input

18

* . * # * * * # * * * # * * * . * .

* . * # * . * # . * . # * * * * * *

* * * # * * * # * * * # * * * * . *

Output

U#O#I#EA

Explanation

As it can be seen that the stars make the image of the alphabets U, O, I, E, and A respectively.

Example 2

Input

12

* . * # . * * * # . * .

* . * # . . * . # * * *

* * * # . * * * # * . *

Output

U#I#A

Explanation

As it can be seen that the stars make the image of the alphabet U, I, and A.

 

Question 8

Problem Statement:-

Here on earth, our 24-hour day is composed of two parts, each of 12hours. Each hour in each part has a corresponding hour in the other parts separated by 12 hours: the hour essentially measures the duration since the start of the day part. For example, 1 hour in the first part of the day is equivalent to 13, which is 1 hour into the second part of the day.Now, consider the equivalent hours that are both prime numbers. We have 3 such instances for a 24-hour 2-part day:

 

5~17

7~19

11~23

 

Accept two natural numbers D, P >1 corresponding respectively to number

of hours per day and number of parts in a day separated by a space. D

should be divisible by P, meaning that the number of hours per part (D/P)

should be a natural number. Calculate the number of instances of

equivalent prime hours. Output zero if there is no such instance.

 

Note that we require each equivalent hour in each part in a day to be a prime number.



Example:

 

Input: 24 2

Output:3 (We have 3 instances of equivalent prime hours: 5~17, 7~19 and

11~23.)

 

Constraints:

 

10 <= D < 500

2 <= P < 50

 

Input:

 

Single line consists of two space separated integers, D and P

corresponding to number of hours per day and number of parts in a day

respectively.

 

Output:

 

Output must be a single number, corresponding to the number of

instances of equivalent prime number, as described above

 

Time Limit:

 

1

 

Examples

 

Example 1

 

Input

 

36 3

 

Output

 

2

 

Explanation

 

In the given test case D = 36 and P = 3

Duration of each day part = 12

2~14~X

3~15~X

5~17~29 – instance of equivalent prime hours

 

7~19~31 – instance of equivalent prime hours

11~23~X

Hence the answers is 2.

 

Example 2

 

Input

 

49 7

 

Output

 

0

 

Explanation

 

Duration of each day part = 7

2~9~X~23~X~37~X

3~X~17~X~31~X~X

5~X~19~X~X~X~47

7~X~X~X~X~X~X

Hence there are no equivalent prime hours.