Programming Sheet – Infosys

Question 1:
While playing an RPG game, you were assigned to complete one of the hardest quests in this
game. There are n monsters you’ll need to defeat in this quest. Each monster i is described
with two integer numbers – poweri and bonusi. To defeat this monster, you’ll need at
least poweri experience points. If you try fighting this monster without having enough
experience points, you lose immediately. You will also gain bonusi experience points if you
defeat this monster. You can defeat monsters in any order.

The quest turned out to be very hard – you try to defeat the monsters but keep losing
repeatedly. Your friend told you that this quest is impossible to complete. Knowing that,
you’re interested, what is the maximum possible number of monsters you can defeat?

Input Format:

• The first line contains an integer, n, denoting the number of monsters. The next line
contains an integer, e, denoting your initial experience.
• Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer, poweri,
which represents power of the corresponding monster.
• Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer, bonusi,
which represents bonus for defeating the corresponding monster.

Sample Input:

2
123
78
130
10
0

Sample Output:

Explanation:

• Initial experience level is 123 points.

• Defeat the first monster having power of 78 and bonus of 10. Experience level is now
123+10=133.
• Defeat the second monster.
Question 2:

Your birthday is coming soon and one of your friends, Alex, is thinking about a gift for you.
He knows that you really like integer arrays with interesting properties.

He selected two numbers, N and K and decided to write down on paper all integer arrays of
length K (in form a[1], a[2], …, a[K]), where every number a[i] is in range from 1 to N, and,
moreover, a[i+1] is divisible by a[i] (where 1 < i <= K), and give you this paper as a
birthday present.

Alex is very patient, so he managed to do this. Now you’re wondering, how many different
arrays are written down on this paper?

Since the answer can be really large, print it modulo 10000.

Input:

• The first line contains an integer, n, denoting the maximum possible value in the
arrays.
• The next line contains an integer, k, denoting the length of the arrays.

Sample Input:
2
1

Sample Output:
2
Explanation:
The required length is 1, so there are only two possible arrays: [1] and [2].
Question 3:
You have an array A of N integers A1 A2 ... An. Find the longest increasing subsequence Ai1
Ai2 ... Ak
(1 <= k <= N) that satisfies the following condition:
For every adjacent pair of numbers of the chosen subsequence Ai[x] and Ai[x+1] (1 < x <
k), the expression (Ai[x] & Ai[x+1]) * 2 < (Ai[x] | Ai[x+1]) is true

Note: ‘&’ is the bitwise AND operation, ‘ | ‘ is the bit-wise OR operation

Input:

1. The first line contains an integer, N, denoting the number of elements in A.

2. Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing
Ai.

Sample Input:

5
15
6
5
12
1

Sample Output:

Explanation:

One possible subsequence is: 5 12

Question 4:
You have been given a string S of length N. The given string is a binary string which consists
of only 0’s and ‘1’s. Ugliness of a string is defined as the decimal number that this binary
string represents.
Example:
• “101” represents 5.
• “0000” represents 0.
• “01010” represents 10.

There are two types of operations that can be performed on the given string.

• Swap any two characters by paying a cost of A coins.

• Flip any character by paying a cost of B coins
• flipping a character means converting a ‘1’to a ‘0’or converting a ‘0’ to a ‘1’.

Initially, you have been given coins equal to the value defined in CASH. Your task is to
minimize the ugliness of the string by performing the above mentioned operations on it.
Since the answer can be very large, return the answer modulo 10^9+7.

Note:
• You can perform an operation only if you have enough number of coins to perform it.
• After every operation the number of coins get deducted by the cost for that operation.

Input Format
• The first line contains an integer, N, denoting the number of character in the string
• The next line contains a string, S, denoting the the binary string
• The next line contains an integer, CASH, denoting the total number of coins present
initially
• Next will contains an integer, A, denoting the cost to swap two characters.
• Then the next line contains an integer, B, denoting the cost to flip a character.

Constraints
• 1 <= N <= 10^5
• 1< len(S)<= 10^5
• 1<=CASH <=10^5
• 1<=A<=10^5
• 1<=B<=10^5

Sample Input:
4
1111
7
1
2

Sample Output: 1

Explanation: 3 flips can be used to create “0001” which represents 1.

Question 5:
Khaled has an array A of N elements. It is guaranteed that N is even. He wants to choose at
most N/2 elements from array A. It is not necessary to choose consecutive elements. Khaled
is interested in XOR of all the elements he chooses. Here, XOR denotes the bitwise XOR
operation.

For example:

• If A=[2,4,6,8], then khaled can choose the subset [2,4,8] to achieve XOR=(2 XOR 4
XOR 8)=14.

Khaled wants to maximize the XOR of all the elements he chooses. Your task is to help
khaled to find the max XOR of a subset that he can achieve by choosing at most N/2
elements?

Input format:

• The first line contains an integer, N, denoting the number of elements in A.

• Each line i of the N subsequent lines(where 0<=i<=N) contains an integer describing
Ai.

Constraints

• 1<=N<=120
• 1<=A[i]<=10^6

Sample Input:

2
1
2

Sample Output:
2

Explanation: N=2, A=[1,2] khaled can choose the subset[2]. The xor of the elements in the
subset is 2. And the number of elements in the subset is 1 which is less than N/2.
Question 6:
Wael is well-known for how much he loves the bitwise XOR operation, while kaito is well
known for how much he loves to sum numbers, so their friend Resli decided to make up a
problem that would enjoy both of them. Resil wrote down an array A of length N, an integer
K and he defined a new function called Xor- sum as follows

• Xor-sum(x)=(x XOR A[1])+(x XOR A[2])+(x XOR A[3])+…………..+(x XOR

A[N])
Can you find the integer x in the range [0,K] with the maximum Xor-sum (x) value?
Print only the value.

Input format:

• The first line contains integer N denoting the number of elements in A.

• The next line contains an integer, k, denoting the maximum value of x.
• Each line i of the N subsequent lines(where 0<=i<=N) contains an integer describing
Ai.

Constraints:

• 1<=N<=10^5
• 0<=K<=10^9
• 0<=A[i]<=10^9

Sample Input:
1
0
989898

Sample Output:
989898

Explanation:
Xor_sum(0)=(0^989898)=989898
Question 7:
One of the first lessons IT students learn is the representation of natural numbers in the binary
number system (base 2) This system uses only two digits, 0 and 1. In everyday life we use for
convenience the decimal system (base 10) which uses ten digits, from 0 to 9. In general, we
could use any numbering system.

Computer scientists often use systems based on 8 or 16. The numbering system based on K
uses K digits with a value from 0 to K-1. Suppose a natural number M is given, written in the
decimal system To convert it to the corresponding writing in the system based on K, we
successively divide M by K until we reach a quotient that is less than K

The representation of M in the system based on K is formed by the final quotient (as first
digit) and is followed by the remainder of the previous divisions.

For example:

• If M=122 and K=8, 122 in base 10= 172 in base 8 This means that the number
• In decimal system = 172 in octal system.
• 172 in base 8 = 1*8^2 + 7*8 + 2 = 122

You made the following observation in applying the above rule of converting natural
numbers to another numbering system

• In some cases in the new representation all the digits of the number are the same. For
example: 63 in base 10= 333 in base 4

Given a number M in its decimal representation, your task is find the minimum base B such
that in the representation of M at base B all digits are the same.

Input Format

• The first line contains an integer, M, denoting the number given

Constraints

• 1 <= M = 10^12

Sample Input:
41

Sample Output:
40

Explanation: Here 41 in base 40. will be 11 so it has all digits the same, and there is no
smaller base satisfying the requirements
Question 8:
Andy wants to go on a vacation to de-stress himself. Therefore, he decides to take a trip to an
island. It is given that he has as many consecutive days as possible to rest, but he can only
make one trip to the island. Suppose that the days are numbered from 1 to N. Andy has M
obligations in his schedule, which he has already undertaken and which correspond to some
specific days. This means that ith obligation is scheduled for day Di. Andy is willing to
cancel at most k of his obligations in order to take more holidays.

Your task is to find out the maximum days of vacation Andy can take by cancelling at most K
of his obligations.

Input Format

• The first line contains an integer N, denoting the total number of days
• The next line contains an integer M denoting the total number of obligations.
• The next line contains an integer K denoting the largest number of obligations he
could cancel
• Each line i of the M subsequent lines (where 0<=i<=M) contains an integer describing
Di.

Constraints

• 1<=N<=10^6
• 1<=M<=2*10^6
• 1<=K<=2*10^6
• 1<=D[i]<=10^6

Sample Input:
10
5
2
6
9
3
2
7

Sample Output:
5

Explanation: Here he could cancel his 3rd and 4th obligation which makes vacation length
5.
Question 9:

Abhijeet is one of those students who tries to get his own money by part time jobs in various
places to fill up the expenses for buying books. He is not placed in one place, so what he
does, he tries to allocate how much the book he needs will cost, and then work to earn that
much money only. He works and then buys the book respectively. Sometimes he gets more
money than he needs so the money is saved for the next book. Sometimes he doesn’t. In that
time, if he has stored money from previous books, he can afford it, otherwise he needs money
from his parents.

Now his parents go to work and he can’t contact them amid a day. You are his friend, and
you have to find how much money minimum he can borrow from his parents so that he can
buy all the books.

He can Buy the book in any order.

Function Description: Complete the function with the following parameters:

Name Type Description

N Integer How many Books he has to buy that day.
EarnArray[ ] Integer array Array of his earnings for the ith book
CostArray[ ] Integer array Array of the actual cost of the ith book.

Constraints:
• 1 <= N <= 10^3
• 1 <= EarnArray[i] <= 10^3
• 1 <= CostArray[i] <= 10^3

Input Format:

• First line contains N.

• Second N lines contain The ith earning for the ith book.
• After that N lines contain The cost of the ith book.

Output Format: The minimum money he needs to cover the total expense.

Sample Input 1:
3
[3 4 2]
[5 3 4]

Sample Output: 3

Explanation: At first, he buys the 2nd book, which costs 3 rupees, so he saves 1 rupee. Then
he buys the 1st book, that takes 2 rupees more. So, he spends his stored 1 rupee and hence he
needs 1 rupee more. Then he buys the last book.
Question 10:
Shovon is an HR in a renowned company and he is assigning people to work. Now he is
assigning people work in a fashion where if he assigns some work a work of cost 2, the next
person will be strictly getting a job with cost equal or more than 2. Given that Shovon’s
company has infinite work and a number of employees, how many distributions can be
possible. The cost of jobs can go 0 to 9.

Function Description:

Complete the special_numbers function in the editor below. It has the following parameter(s):

Parameters:

Name Type Description

N Integer The number of depts.
arr[ ] Integer array The number of employees in each dept..
Return: The function must return an INTEGER denoting the sum of answers for all distinct
distributions.

Constraints:

• 1 <= n <= 100

• 1 <= arr[i] <= 200

Sample Input:
2
4
1

Sample Output:
725

Explanation:
The ans if m = 1 is 10, which is all numbers from 0 to 9
The ans for m = 2 is 55
The answer for m = 3 is 220
The answer for m = 4 is 715
So fun(4) + fun(1) = 725