Infosys Coding Questions and Answer for SP and DSE role
Infosys Coding Questions and Answers
Infosys SP and DSE Coding 2023 Question and Answers are explained on this page. Coding round is one of the most important round for getting role for SP and DSE profile.
This section help you in analysing the difficulty level of the problem asked in Infosys. Practising Infosys coding question and answer help you in understanding the difficulty level and question pattern for coding round.
Below you will find Similar pattern based Infosys Coding Round Questions and their solutions in different languages. You must need to prepare the coding questions of Infosys exam for scoring good score.
Coding Test Format
- Coding round contains 3 questions that will have to be attended in 3 hours.
- Each questions have different difficulty level.
- There is one Easy problem based on Algorithm , Aptitude and Data structures.
- One of the problem is of Medium level and that problem is based on Greedy Algorithm.
- One is of Hard difficulty level, and usually based on Dynamic Programming.
| No. Of Questions | Marks per question |
|---|---|
| Question 1 | 20 |
| Question 2 | 30 |
| Question 3 | 50 |
Question 1 –Easy level –
- Simple Question that can be solved by basic applications of Aptitude, Algorithm and Data Structures.
Question 2 – Medium Level – Usually a question based on Greedy Algorithm
- A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. Types of greedy problems are-:
- Pure Greedy Algorithms
- Orthogonal Greedy Algorithms
- Relaxed Greedy Algorithms
Question 3 – Hard level – Usually a question based on Dynamic Programming
- DP is an algorithmic technique for solving an optimisation problem by breaking it down into simpler subproblems and utilising the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.
- Principles of Dynamic Programming-:
- Breaking the problem down into subproblems and calculating their values. Next time, upon encountering the same subproblem, the value can be reused instead of recalculation
- Avoid repeated work by remembering partial results, a common approach for performance enhancements.
Check more about Infosys online exam syllabus by clicking the link given below :
Question 1
Problem Statement:
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?
(Question difficulty level: Hardest)
Input:
- 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.
| Input | Output | Output Description |
|---|---|---|
| 2 123 78 130 10 0 | 2 |
|
| 3 100 101 100 304 100 1 524 | 2 |
|
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Main
{
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int exp = s.nextInt();
int monst[] = new int[n];
int bonus[] = new int[n];
for (int i = 0; i < n; i++) {
monst[i] = s.nextInt();
}
for (int i = 0; i < n; i++) {
bonus[i] = s.nextInt();
}
class Monster {
private final int power, bonus;
public Monster(int power, int bonus){
this.power = power;
this.bonus = bonus;
}
}
Monster[] monsters = new Monster[n];
for(int i = 0; i < n; i++)
monsters[i] = new Monster(monst[i], bonus[i]);
Arrays.sort(monsters, Comparator.comparingInt(m -> m.power));
int count = 0;
for(Monster m: monsters){
if(exp < m.power) break;
exp += m.bonus;
++count;
}
System.out.println(count);
}
}
n = int(input())
lev = int(input())
p = []
b = []
a = []
ans = 0
for i in range(n):
p.append(int(input()))
for j in range(n):
b.append(int(input()))
for k in range(n):
a.append([p[k], b[k]])
a.sort()
for z in a:
if z[0] > lev:
break
lev += z[1]
ans += 1
print(ans)
#include<iostream> #include<map>
Question 2
Problem Statement:
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.
| Input | Output | Output Description |
|---|---|---|
| 2 1 | 2 | The required length is 1, so there are only two possible arrays: [1] and [2]. |
| 2 2 | 3 | All possible arrays are [1, 1], [1, 2], [2, 2]. [2, 1] is invalid because 1 is not divisible by 2. |
| 3 2 | 5 | All possible arrays are [1, 1], [1, 2], [1, 3], [2, 2], [3, 3]. |
import java.util.*;
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int k, n;
n = sc.nextInt();
k = sc.nextInt();
System.out.println(countt(n, k));
}
static int counter(int n, int k) {
int count = 0;
if (k == 1)
return n;
else {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j % i == 0)
count++;
}
}
}
return count;
}
static int countt(int n, int k) {
if (k == 1)
return n;
if (k == 2) {
return counter(n, k);
}
int mid = k / 2;
int x = countt(n, k - mid);
int y = counter(n, mid);
return x + y - 1;
}
}
def counter(n, k):
num = 0
if k == 1:
return n
else:
for i in range(1, n + 1):
for j in range(1, n + 1):
if j % i == 0:
num += 1
return num
def count(n, k):
if k == 1:
return n
if k == 2:
return counter(n, k)
mid = k // 2
x = count(n, k - mid)
y = counter(n, mid)
return x + y - 1
n = int(input())
k = int(input())
print(count(n, k))
Question 3
Problem Statement:
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:
- 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.
Sample cases:
| Input | Output | Output Description |
|---|---|---|
5 | 2 | One possible subsequence is: 5 12 |
6 | 2 | One possible subsequence is: 2 15 |
7 | 3 | One possible subsequence is: 2 8 17 |
#include<bits/stdc++.h>
using namespace std;
int sub(int arr[], int i, int n, int prev){
if(i == n)
return 0;
int a = sub(arr, i + 1, n, prev);
int b = 0;
if (arr[i] > prev)
b = 1 + sub(arr, i + 1, n, arr[i]);
return max(b, a);
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0; i< n; i++)
cin>>arr[i];
int res = sub(arr, 0, n, 0);
cout<< res;
}
class Main
{
public static int LIS(int[] arr, int i, int n, int prev)
{
if (i == n) {
return 0;
}
int excl = LIS(arr, i + 1, n, prev);
int incl = 0;
if (arr[i] > prev) {
incl = 1 + LIS(arr, i + 1, n, arr[i]);
}
return Integer.max(incl, excl);
}
public static void main(String[] args)
{
int[] arr = { 15, 6, 5, 12, 1 };
System.out.print("The length of the LIS is "
+ LIS(arr, 0, arr.length, Integer.MIN_VALUE));
}
}
def sub(arr, i, n, prev=0):
if i == n:
return 0
a = sub(arr, i + 1, n, prev)
b = 0
if arr[i] > prev:
b = 1 + sub(arr, i + 1, n, arr[i])
return max(b, a)
n = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
print("Length of Bitwise subsequence will be", sub(arr, 0, len(arr)))
Question 4
Asked in Infosys Placment Paper – Feb 2022
Problem Statement :
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 1 :
4
1111
7
1
2
Sample Output 1 :
1
Explanation:
3 flips can be used to create “0001” which represents 1.
Sample Input 2:
6
111011
7
1
3
Sample Output 2:
7
Explanation:
First swap 0 with the most significant 1, then use flip twice first on index one and then on index two “111011”=>”0111111″=>”001111″=>”000111″ the value represented is 7.
Sample Input 3:
6
111011
7
3
2
Sample Output 3:
3
Explanation:
Flip the 3 most significant characters to get “000011” : the value represented by this string is 3.N
#include<bits/stdc++.h>
using namespace std;
string s;
int n, cash, a, b;
void swapf ()
{
int i;
for (int a = 0; a < s.length (); a++)
if (s[a] == '1')
{
i = a;
break;
}
int j = s.length () - 1;
while (j > i)
{
if (cash < a)
break;
if (s[j] == '0')
{
if (s[i] == '0')
i++;
else
{
swap (s[i], s[j]);
cash -= a;
j--;
}
}
else
j--;
}
}
void flipf ()
{
int i;
for (int a = 0; a < s.length (); a++)
if (s[a] == '1')
{
i = a; break;
}
while (cash >= b)
{
if (i == s.length ())
break;
if (s[i] == '1')
{
s[i] = '0';
i++;
cash -= b;
}
}
}
int main ()
{
cin >> n >> s >> cash >> a >> b;
if (a < b)
{
swapf ();
flipf ();
}
else
{
flipf ();
swapf ();
}
cout << stoull (s, 0, 2);
}
import java.util.*;
class Main
{
static String str;
static int cash, n, a, b;
static void swapf ()
{
char s[] = str.toCharArray ();
int i = 0;
for (int a = 0; a < s.length; a++)
if (s[a] == '1')
{
i = a;
break;
}
int j = s.length - 1;
while (j > i)
{
if (cash < a)
break;
if (s[j] == '0')
{
if (s[i] == '0')
i++;
else
{
char temp = s[i];
s[i] = s[j];
s[j] = temp;
cash -= a;
j--;
}
}
else
j--;
}
str = new String (s);
}
static void flipf ()
{
char s[] = str.toCharArray ();
int i = 0;
for (int a = 0; a < s.length; a++)
if (s[a] == '1')
{
i = a;
break;
}
while (cash >= b)
{
if (i == s.length)
break;
if (s[i] == '1')
{
s[i] = '0';
i++;
cash -= b;
}
}
str = new String (s);
}
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
n = sc.nextInt ();
str = sc.next ();
cash = sc.nextInt ();
a = sc.nextInt ();
b = sc.nextInt ();
if (a < b)
{
swapf ();
flipf ();
}
else
{
flipf ();
swapf ();
}
System.out.println (Integer.parseInt (str, 2));
}
}
# N = int(input())
# S = list(input())
# Cash = int(input())
# A = int(input())
# B = int(input())
N = 6
S = list("111011")
Cash = 7
A = 1
B = 3
def swap():
global Cash
Rs = S.copy()
S[S.index('1')], S[''.join(S).rindex('0')] = S[''.join(S).rindex('0')], S[S.index('1')]
if Rs == S:
flip()
else:
Cash -= A
def flip():
global Cash
S[S.index('1')] = '0'
Cash -= B
while Cash > A or Cash > B:
if A < B and '0' in S:
swap()
else:
flip()
print(int(''.join(S), 2))
Question 5
Asked in Infosys Placment Paper – Feb 2022
Problem Statement :
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 1
2
1
2
Sample Output 1
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.
Sample Input 2
4
1
2
4
7
Sample Output 2
7
Explanation:
N=4, A=[1,2,4,7] Khaled can choose the subset [7]. The xor of the elements in the subset is 7, and the number of elements in the subset is 1 which is less than N/2.
#include<bits/stdc++.h>
using namespace std;
int main ()
{
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) cin >> arr[i];
int M = 1 << 20;
int dp[M];
char res[M];
for (int i = 1; i < M; i++)
dp[i] = INT_MAX;
for (int i = 0; i < n; i++)
{
if (arr[i] == 0)
continue;
for (int j = 0; j < M; j++)
res[j] = 0;
for (int k = 0; k < M; k++) { if (res[k] == 1) continue; if (dp[k] > dp[k ^ arr[i]])
dp[k] = dp[k ^ arr[i]] + 1;
else if (dp[k ^ arr[i]] > dp[k])
dp[k ^ arr[i]] = dp[k] + 1;
res[k ^ arr[i]] = 1;
}
}
int j = M - 1, k = n >> 1;
while (dp[j] > k)
j--;
cout << j;
return 0;
}
import java.util.*;
class Main
{
public static void main (String[]args)
{
final int N = 120, M = 1 << 20;
int dp[] = new int[M];
char res[] = new char[M];
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt ();
for (int i = 1; i < M; i++)
dp[i] = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i)
{
if (arr[i] == 0)
continue;
for (int j = 0; j < M; ++j)
res[j] = 0;
for (int k = 0; k < M; ++k) { if (res[k] == 1) continue; if (dp[k] > dp[k ^ arr[i]])
dp[k] = dp[k ^ arr[i]] + 1;
else if (dp[k ^ arr[i]] > dp[k])
dp[k ^ arr[i]] = dp[k] + 1;
res[k ^ arr[i]] = 1;
}
}
int j = M - 1, k = n >> 1;
while (dp[j] > k)
--j;
System.out.println (j);
}
}
from itertools import combinations
def fun(arr, N):
sub = []
max_xor = max(arr)
for i in range(1, N // 2):
comb = combinations(arr, i + 1)
for i in comb:
sub.append(list(i))
for a in sub:
z = 0
for b in a:
z = z ^ b
if z > max_xor:
max_xor = z
return max_xor
N = int(input("Enter Length : "))
arr = []
for i in range(N):
arr.append(int(input(f"Enter {i+1} Element : ")))
if N < 3:
print("Output :", max(arr))
else:
print("Output :", fun(arr, N))
Question 6
Problem Statement :
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
1
0
989898
Sample Output 1
989898
Explanation:
Xor_sum(0)=(0^989898)=989898
Sample Input 2
3
7
1
6
3
Sample Output 2
14
Explanation
Xor_sum(4)=(4^1)+(4^6)+(4^3)=14.
Sample Input 3
4
9
7
4
0
3
Sample Output 3
46
Explanation:
Xor_sum(8)=(8^7)+(8^4) +(8^0)+(8^3)=46.
#include<bits/stdc++.h>
using namespace std;
unordered_map < int, int >L;
int main ()
{
int n, k, m;
cin >> n >> k;
vector < int >v (n);
for (int i = 0; i < n; i++) { cin >> m;
v[i] = m;
int j = 0;
while (m)
{
L[j] += (m & 1);
m >>= 1;
j++;
}
}
int j = 0, K = k, ans = 0, ans2 = 0;
while (K)
{
j++;
K >>= 1;
}
for (int i = j; i > 0; i--)
{
if (L[i - 1] < n - L[i - 1])
ans != 1;
ans <<= 1; } ans >>= 1;
while (ans > k)
{
ans &= 0;
ans <<= 1;
k <<= 1;
}
for (auto i:v)
ans2 += ans ^ i;
cout << ans2;
}
import java.util.*;
class Main
{
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int k = sc.nextInt ();
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt ();
int res = 0, max = Integer.MIN_VALUE;
for (int i = 0; i <= k; i++)
{
res = 0;
for (int j = 0; j < n; j++)
res = res + (i ^ arr[j]);
max = Math.max (res, max);
}
System.out.println (max);
}
}
def Xor_sum(x, arr):
xorSum = sum(arr)
for i in range(1, x):
s = 0
for j in arr:
s += i ^ j
if s > xorSum:
xorSum = s
return xorSum
n = 4
x = 9
arr = [7, 4, 0, 3]
print(Xor_sum(x, arr))
Question 7
Asked in Infosys Placment Paper – Sept 2021
Problem Statement :
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 divisionsFor 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 1 :
41
Sample Output 1 :
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
Sample Input 2 :
34430
Sample Output 2 :
312
Explanation :
Here 34430 in base 312 will have all digits the same and there is no smaller base satisfying the requirements
#include<bits/stdc++.h>
using namespace std;
bool converted (int M, int base)
{
int rem = M % base;
M /= base;
while (M >= base)
{
if (M % base != rem)
return 0;
M /= base;
}
if (M == rem)
return 1;
return 0;
}
int main ()
{
int M;
cin >> M;
int base = 2;
while (converted (M, base) != 1)
{
base++;
}
cout << base;
return 0;
}
import java.util.*;
class Main
{
public static boolean convertBase (int m, int base)
{
int rem = m % base;
m = m / base;
while (m >= base && (m % base == rem))
m = m / base;
if (m == rem)
return true;
return false;
}
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int m = sc.nextInt ();
int base = 2;
while (convertBase (m, base) != true)
base++;
System.out.println (base);
}
}
def convertBase(m, base):
rem = m % base
m = m // base
while m >= base and (m % base == rem):
m = m // base
if m == rem:
return True
return False
m = int(input())
base = 2
while not convertBase(m, base):
base = base + 1
print(base)
Question 8
Asked in Infosys Placment Paper – Sept 2021
Problem Statement :
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 canceling 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 1:
10
5
2
6
9
3
2
7
Sample Output 1 :
5
Explanation:
Here he could cancel his 3rd and 4th obligation which makes vacation length 5.
Sample input 2:
7
2
0
3
4
Sample Output 2:
3
Explanation:
Here he could not cancel any obligation since K=0, so the vacation length is 3.
#include<bits/stdc++.h>
using namespace std;
unordered_map < int, int >L;
int main ()
{
int n, m, k;
cin >> n >> m >> k;
vector < int >v (m);
for (int i = 0; i < m; i++) cin >> v[i];
sort (v.begin (), v.end ());
int st = 0, en = k, ans;
if (k > m)
{
cout << n;
return 0;
}
if (k < m)
ans = v[en] - 1;
for (int j = en + 1; j < m; j++)
{
ans = max (ans, v[j] - v[st] - 1);
st++;
}
ans = max (ans, n - v[st]);
cout << ans;
}
import java.util.*;
class Main
{
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int m = sc.nextInt ();
int k = sc.nextInt ();
int arr[] = new int[n];
for (int i = 0; i < m; i++) arr[i] = sc.nextInt (); int ans = 0; Arrays.sort (arr); if (k > 0)
{
for (int i = k + 1; i <= m + 2; i++)
ans = Math.max (ans, arr[i] - arr[i - k - 1] - 1);
}
else
{
int j = 0;
while (arr[j] == 0)
j++;
int count = 0;
for (int i = 1; i <= n; i++)
{
count++;
if (j < n && (i == arr[j]))
{
count = 0;
j++;
}
ans = Math.max (count, ans);
}
}
System.out.println (ans);
}
}
n = int(input())
m = int(input())
k = int(input())
arr = [0] * n
for i in range(m):
arr[i] = int(input())
ans = 0
arr.sort()
if k > 0:
for i in range(k + 1, m + 3, 1):
ans = max(ans, arr[i] - arr[i - k - 1] - 1)
else:
j = 0
while arr[j] == 0:
j = j + 1
count = 0
for i in range(1, n + 1, 1):
count += 1
if j < n and (i == arr[j]):
count = 0
j += 1
ans = max(count, ans)
print(ans)
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Question 9
Problem Statement :
You need to build a road in a rugged terrain. You know the sea level of each segment of the rugged terrain, i.e., the i-th segment is Li meters from sea level.
You need to transform the terrain into a strictly downward sloping terrain for the road, i.e., for each i-th segment where 2 <= i <= N, resultant Li-1 > Li. To do so, you employ a powerful digging team to help you dig and reduce the sea level of the segments. On day D, the team can reduce the sea level for each segment that you scheduled that day by 2D-1 meters each.
You are allowed to assign the team to dig on multiple segments and/or dig on the same segments for multiple days.
Your task is to find the minimum number of days needed to transform the terrain as per your requirements.
Input Format
N :: INTEGER
The first line contains an integer, N, denoting the number of elements in L. N :: 1 -> 10^5
L :: INTEGER ARRAY
Each line i of the N subsequent lines (where 0 < i ≤ N) contains an integer describing Li, the sea level of the i-th segment. L[i] :: -10^9 -> 10^9
Sample Input 1:
2
3
3
Sample Output 1 :
1
Sample input 2:
2
5
-3
Sample Output 2:
0
#include <bits/stdc++.h>
#define int long long int
using namespace std;
int32_t main()
{
int n;
cin>>n;
int a[n];
for(int i =0; i < n; i++) { cin >> a[i];
}
int max_dig = 0;
for(int i =0; i < n-1; i++)
{
if(a[i] <= a[i+1])
{
max_dig = max(max_dig,(a[i+1]-a[i]+1));
a[i+1] = a[i] -1;
}
}
int ans = ceil(sqrt(max_dig));
cout<< ans << endl;
}
import java.util.*;
import java.lang.Math;
class Main{
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] a = new int[n];
for(int i =0; i< n; i++)
{
a[i] = s.nextInt();
}
int max_dig = 0;
for(int i =0; i< n-1; i++)
{
if(a[i]<=a[i+1])
{
max_dig = Math.max(max_dig,(a[i+1]-a[i]+1));
a[i+1] = a[i] -1;
}
}
int ans = (int)Math.sqrt(max_dig);
System.out.println(ans);
}
}
Question 10
Problem Statement :
You are given an array of size N. You need to change this array into a mountain. By mountain we mean, the either ends of the array should have equal elements. Then as we move towards the middle from both ends, the next element is just one more than the previous one. So, it would have a peak in the middle and decrease if you go towards either end, just like a mountain.
Examples of mountains are [1, 2, 3, 2, 1] or [6, 7, 8, 8, 7, 6]. But the array [1, 2, 4, 2, 1] is not a mountain because from 2 to 4 the difference is 2. The array [1, 2, 3, 1] is also not a mountain because the elements 2 and 3 are not equal from both ends.
You need to find the minimum number of elements that should be changed to make the array a mountain. You can make the elements negative or zero as well.
Input Format
N :: INTEGER
The first line contains an integer, N, denoting the number of elements in array. N :: 1 -> 10^5
array :: INTEGER ARRAY
Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing i-th element of array. array[i] :: 1 -> 10^6
Sample Input 1:
5
1
2
3
4
5
Sample Output 1 :
2
Sample input 2:
9
1
1
1
2
3
2
1
1
1
Sample Output 2:
4
#include <iostream>
using namespace std;
int mountain(int arr[], int n){
int count=0;
if(n%2==0){
int m2 = n/2;
int m1 = m2-1;
if(arr[m1] == arr[m2]){
for(int i =m1-1; i>=0; i--){
if(arr[i] != (arr[i+1] -1)){
count++;
arr[i] = (arr[i+1]-1);
}
}
}
else if(arr[m1] != arr[m2]){
arr[m2] = arr[m1];
for(int i =m1-1; i >= 0; i--){
if(arr[i] != (arr[i+1] -1)){
count++;
arr[i] = (arr[i+1]-1);
}
}
}
int j = m1-1;
for(int i =m2+1; i < n; i++){
if(arr[i] != arr[j]){
count ++;
}
j--;
}
return count;
}
else{
int mid = n/2;
for(int i = mid-1; i >= 0; i--){
if(arr[i] =! (arr[i+1]-1)){
count++;
arr[i] = (arr[i+1]-1);
}
}
int j = mid-1;
for(int i = mid+1;i> n;
int arr[n];
for(int i =0; i> arr[i];
}
cout << mountain(arr,n);
}
import java.util.Scanner;
class Main{
public static int mountain(int[] arr, int n){
int count=0;
if(n%2==0){
int m2 = n/2;
int m1 = m2-1;
if(arr[m1] == arr[m2]){
for(int i =m1-1; i>=0; i--){
if(arr[i] != (arr[i+1] -1)){
count++;
arr[i] = (arr[i+1]-1);
}
}
}
else if(arr[m1] != arr[m2]){
arr[m2] = arr[m1];
for(int i =m1-1; i>=0; i--){
if(arr[i] != (arr[i+1] -1)){
count++;
arr[i] = (arr[i+1]-1);
}
}
}
int j = m1-1;
for(int i =m2+1; i=0; i--){
if(arr[i] != (arr[i+1]-1)){
count++;
arr[i] = (arr[i+1]-1);
}
}
int j = mid-1;
for(int i = mid+1;i < n; i++){
if(arr[i] !=arr[j]){
count++;
}
j--;
}
return count;
}
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int arr[] = new int[n];
for(int i =0; i < n; i++){
arr[i]= s.nextInt();
}
System.out.println(mountain(arr,n));
}
}
Question 11
Problem Statement :
You have an interesting string S of length N. It is interesting because you can rearrange the characters of this string in any order. You want to cut this string into some contiguous pieces such that after cutting, all the pieces are equal to one another.
You can’t rearrange the characters in the cut pieces or join the pieces together. You want to make the number of pieces as large as possible. What is the maximum number of pieces you can get?
Note: You can observe that you may not want to cut the string at all, therefore the number of pieces is 1. Hence, the answer always exists.
Input Format
S :: STRING
The first line contains a string, S, denoting the string.
length(S) :: 1 -> 2 * 10^5
Sample Input 1:
zzzzz
Sample Output 1 :
5
Sample input 2:
ababcc
Sample Output 2:
2
Sample input 2:
abccdcabacda
Sample Output 2:
2
#include<iostream>
#include<unordered_map>
#include<string>
#include<math.h>
using namespace std;
int ans(string s){
unordered_map map;
for(int i =0; i map[s[i]]){
val = map[s[i]];
key = map[s[i]];
//we will get the smallest number.
}
}
return val;
}
int main()
{
string s;
cin>>s;
cout<< ans(s);
return 0;
}
import java.util.*;
class Main {
public static void main(String[] args) {
String s;
Scanner sc = new Scanner(System.in);
s = sc.next();
System.out.print(ans(s));
}
static int ans(String s) {
HashMap map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if (!map.containsKey(s.charAt(i))) {
map.put(s.charAt(i), 1);
} else {
map.put(s.charAt(i),map.getOrDefault(s.charAt(i), 1)+1);
}
}
int key = 100000;
int val = 0;
for (int i = 0; i < s.length(); i++) {
if (key > map.get(s.charAt(i))) {
val = map.get(s.charAt(i));
key = map.get(s.charAt(i));
// we will get the smallest number.
}
}
return val;
}
}
Question 12
Problem Statement :
Today you decided to go to the gym. You currently have energy equal to E units. There are N exercises in the gym. Each of these exercises drains Ai amount of energy from your body.
You feel tired if your energy reaches 0 or below. Calculate the minimum number of exercises you have to perform such that you become tired. Every unique exercise can only be performed at most 2 times as others also have to use the machines.
If performing all the exercises does not make you feel tired, return -1.
Input Format
E :: INTEGER
The first line contains an integer, E, denoting the Energy.
E :: 1 -> 10^5
N :: INTEGER
The next line contains an integer, N, denoting the number of exercises. N :: 1 -> 10^5
A :: INTEGER ARRAY
Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing the amount of energy drained by i-th exercise.
A[i] :: 1 -> 10^5
Sample Input 1:
6
2
1
2
Sample Output 1 :
4
Sample input 2:
10
2
1
2
Sample Output 2:
-1
Sample input 3:
2
3
1
5
2
Sample Output 3:
1
#include <iostream>
using namespace std;
int exercise(int arr[], int test, int energy){
//check if some input == energy , if yess then return 1.
for(int i =0; i<test; i++){
if(arr[i] == energy){
return 1;
}
}
int sum =0;
int ans =0;
int ans1=0;
for(int i=0; i<test; i++){ sum = sum + arr[i]; if(sum >=energy){
ans = i+1;
return ans;
}
}
sum =0;
for(int i =0; i<test; i++){ sum = sum + arr[i]; if(2*sum >= energy){
ans1 = 2*(i+1);
return ans1;
}
}
return -1;
}
int main()
{
int energy ;
cin>>energy;
int test;
cin>>test;
int arr[test];
for(int i =0; i<test; i++){ cin>> arr[i];
}
int ans = exercise(arr, test, energy);
cout << ans;
}
import java.util.Scanner;
public class Main {
public static int solution(int nExcercise,int[] arr,int energy){
int sum = 0;
for(int i = 0; i< nExcercise; i++) {
if(arr[i]==energy)
return 1;
}
for(int i =0; i= energy){
return i+1;
}
if(2*sum >= energy){
return 2*(i+1);
}
}
//if sum is not equal to the energy.
return -1;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int energy = s.nextInt();
int nExcercise = s.nextInt();
int[] arr= new int[nExcercise];
for (int i = 0; i < nExcercise; i++)
{
arr[i] = s.nextInt();
}
int ans = solution(nExcercise,arr,energy);
System.out.println(ans);
}
}
Question 13
Problem Statement :
There is a battle between heroes and villains going on. You have M heroes, all of them have the same health H. There are N villains, health of the i-th villain is Vi.
When a hero, with health H battles a villain with health Vi, one of the three scenarios can happen:
if H > Vi: The villain is defeated, and the health of the hero is decreased by Vi if H < Vi: The villain wins, his health is not affected, and the hero is no longer able to fight. if H = Vi: Both are considered defeated, and neither can fight.
The heroes start fighting villains one by one in the same order, first villain 1 then villain 2 and so on. It might be possible that before defeating all the villains, all the heroes are defeated. Therefore, to ensure the victory of the heroes, you want to remove some villains from the front.
Your task is to find the minimum number of villains you need to remove from the front such that the victory of the heroes is guaranteed.
Note: If in the last battle, both the hero and villain are defeated and no more heroes or villains remain, it would still be considered a victory since all the villains are defeated.
Input Format
N :: INTEGER
The first line contains an integer, N, denoting the number of villains N :: 1 -> 2*10^5
M :: INTEGER
The next line contains an integer, M, denoting the number of heroes M :: 1 -> 2*10^5
H :: INTEGER
The next line contains an integer, H, denoting the health of each of the heroes H :: 1 -> 10^9
array :: INTEGER ARRAY
Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing the health of each of the villains.
array[i] :: 1 -> 10^9
Sample Input 1:
4
4
3
3
1
3
3
Sample Output 1 :
0
Sample input 2:
5
3
3
1
2
3
1
1
Sample Output 2:
0
Sample input 3:
5
1
4
1
2
3
1
3
Sample Output 3:
3
#include <iostream>
using namespace std;
int ans(int arr[], int n, int m, int h){
int total = 0;
for(int i =0; i0; i--){
sumh= sumh+arr[i];
if(sumh >= totalhero){
return i;
}
}
}
}
int main()
{
int n;//number of villians.
cin>>n;
int m ; //number of heroes
cin>>m;
int h;//health of hero.
cin>>h;
int arr[n];
for(int i =0; i>arr[i];//health of villians
}
cout<
import java.util.Scanner;
class Main{
public static int ans(int[] arr, int n, int m, int h){
int total = 0;
for(int i =0; i0; i--){
sumh= sumh+arr[i];
if(sumh >= totalhero){
return i;
}
}
}
return 0;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int m = s.nextInt();
int h = s.nextInt();
int arr[] = new int[n];
for(int i =0; i
Login/Signup to comment
#include
using namespace std;
int main()
{
int n, k, m;
cin >> n >> k;
vector arr (n);
for (int i = 0; i > m;
arr[i] = m;
}
int my_sum=accumulate(arr.begin(), arr.end(), 0);
for(int i=0; imy_sum) {
my_sum=s;
}
}
}
cout<<my_sum;
}
When will be open hiring for infosys SP and DSE roles for the 2023 batch
for last question of andy vecation ,for input 10 5 2 2 4 5 7 9 it should have given 4 instead of 5 as o/p
Thanks, sir I got placed in Infosys as a Specialist Programmer due to your Prime Video Course thanks
Hey Guys,
If you are looking for Infosys SP and DSE preparation course, please check out this link :
Click here
Hey what will be the first test include which will be for 180 minutes could you brief me please
Sir your platform has been very useful to me in learning and getting placed!
Thank you so much Likhitha.
We wish you all the best!
Also, guys if you are looking for preparation material which Covers whole Python, Java DSA, Competitive Coding etc and past year’s Infosys InfyTQ coding questions, click here
From where can I get off campus Drive updates?
Hey Muskan, You can get all the off campus updates from here.
Click here
Good platform form to know about coding