# Infosys Coding Questions and Answer for SP and DSE role ## Infosys Coding Questions and Answers

Infosys SP and DSE Coding and Answers 2021-22 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.

## Question 1

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 Solution {    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));    }}`

## Question 2

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. 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 . 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.

`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);    }}`
`#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;}`

## Question 3

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)+(x XOR A)+(x XOR A)+…………..+(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 Solution {    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);    } }`

## Question 4

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 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 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 Solution {    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);    }}`

## Question 5

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 Solution {    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);    }}`