Q1.
You are given an integer N.
You have to choose a set of integers S from the range [1, N-1] such that the product of integers in S is 1 modulo N. This means that if N=5, we can choose set S = [1,2,3] as the product is 6 and 6 modulo 5 is 1.
Find the length of the biggest set S you can choose.
Input Format
The first line contains an integer N, denoting the given integer.
Constraints
1<=N<= 5 * 10^5
Sample Input 1
7
Sample Output 1
5
Explanation:
We can choose set (1,2,3,4,5). Here product = 120 which mod 7 is 1
Sample Input 2
5
Sample Output 2
3
Explanation:
Here we can choose set (1,2,3) where product is 6 and 6 mod 5 =1
Sample Input 3
4
Sample Output 3
1
Explanation
Here we choose only (1)
C Solution
#include <stdio.h>
int fact(int num)
{
if(num>0)
return num * fact(num-1);
else
return 1;
}
int main()
{
int N,i;
scanf("%d",&N);
int a[N-1];
for(i=0;i<N;i++ )
{
a[i]=i+1;
}
for(int x =N-1;x>=1;x--)
{
int y = fact(x);
if (y%N == 1)
{
printf("%d",x);
break;
}
}
return 0;
}
C++ Solution
#include <iostream>
using namespace std;
int fact(int num)
{
if(num>0)
return num * fact(num-1);
else
return 1;
}
int main()
{
int N,i;
cin>>N;
int a[N-1];
for(i=0;i<N;i++ )
{
a[i]=i+1;
}
for(int x =N-1;x>=1;x--)
{
int y = fact(x);
if (y%N == 1)
{
cout<<x;
break;
}
}
return 0;
}
Java
import java.util.Scanner;
public class Main
{
public static int fact(int num)
{
if(num>0)
return num * fact(num-1);
else
return 1;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N,i;
N = sc.nextInt();
int a[] = new int[N];
for(i=0;i<N;i++)
{
a[i]=i+1;
}
for(int x =N-1;x>=1;x--)
{
int y = fact(x);
if (y%N == 1)
{
System.out.print(x);
break;
}
}
}
}
Python
N=int(input())
a=[]
def fact(num):
if num>0:
return num * fact(num-1)
else:
return 1
for i in range (0,N-1):
a.append(i+1)
for x in range (N-1,0,-1):
y=fact(x)
if(y%N)==1:
print(x)
break
Q2.
You are given an array of size N.
An array A is considered a summer array if all the even values in A are on one side and odd values are on the other side.
You are allowed to swap two adjacent elements in A in one operation. Find the minimum swap operations required to change A into a summer array.
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 A[i].
Constraints
1<= N <= 10^5
1 <= A[i] <= 10^5
Sample Input 1
3
1
2
2
Sample Output 1
0
Explanation:
Here N=3 A= [1,2,2]. 0 swaps are required here as the odd number is already on the left and all the even number are already on the right
Sample Input 2
3
1
2
1
Sample Output 2
1
Explanation:
Here N =3 A=[1,2,1]. We can swap 2 at 1st index with 1 at 0th index after which A becomes [2,1,1] satisfying the condition.
Sample Input 3
6
1
2
3
4
5
6
Sample Output 3
3
Explanation:
Here N =6 A= [1,2,3,4,5,6] We have to swap 4 one time to right and 2 two times to right making A = [1,3,5,2,4,6]
C Solution
#include <stdio.h>
int main()
{
int N,swap=0,i;
scanf("%d",&N);
int a[N];
for(int i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<N;i++)
{
for(int j=i;j<N-1;j++)
{
if (((a[j])%2==0) && (a[j+1]%2==1))
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
swap++;
break;
}
}
}
printf("%d",swap);
return 0;
}
C++ Solution
#include <iostream>
using namespace std;
int main()
{
int N,swap=0,i;
cin>>N;
int a[N];
for(int i=0;i<N;i++)
{
cin>>a[i];
}
for(i=0;i<N;i++)
{
for(int j=i;j<N-1;j++)
{
if (((a[j])%2==0) && (a[j+1]%2==1))
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
swap++;
break;
}
}
}
cout<<swap;
return 0;
}
Java
import java.util.Scanner;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i,swap=0;
int N = sc.nextInt();
int a[] = new int[N];
for(i=0;i<N;i++)
{
a[i]=sc.nextInt();
}
for(i=0;i<N;i++)
{
for(int j=i;j<N-1;j++)
{
if (((a[j])%2==0) && (a[j+1]%2==1))
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
swap++;
break;
}
}
}
System.out.println(swap);
}
}
Python
N=int(input())
swap=0
a=[]
for i in range(0,N):
a.append(int(input()))
for i in range(0,N):
for j in range(i,N-1):
if ((a[j]%2==0) and (a[j+1]%2==1)):
temp=a[j]
a[j] = a[j+1]
a[j+1] = temp
swap=swap+1
break
print(swap)
Q3.
There are N buckets numbered 11 through N. The buckets contain balls; each ball has a color between 11 and K. Let's denote the number of balls with color j that are initially in bucket i by ,ai,j?.
For each i from 1 to N−1 (in this order), someone draws a ball uniformly at random from bucket i and puts it into bucket i+1, then continues to draw the next ball. After putting a ball in bucket N, this person draws a ball, again uniformly at random, from bucket N.
For each color from 1 to K, find the probability that the ball drawn from bucket N has this color.
Input
- The first line of the input contains two space-separated integers N and K.
- N lines follow. For each i (1≤ i ≤N), the i-th of these lines contains K space-separated integers ai,1?,ai,2?,…,ai,K?.
Output
Print a single line containing K space-separated real numbers. For each valid i, the i-th of these numbers should denote the probability that the last drawn ball has color i. your answer will be considered correct if absolute or relative error does not exceed 10^6
Sample Input 1
2 2
0 1
1 1
Sample Output 1
0.333333 0.666667
C Solution
#include<stdio.h>
int main(){
int N,K,i,j;
scanf("%d%d",&N,&K);
float a[N][K],sum[N],p[K];
for(i=0;i<N;i++){
sum[i]=0;
for(j=0;j<K;j++){
scanf("%f",&a[i][j]);
sum[i]=sum[i]+a[i][j];
}
}
for(j=0;j<K;j++){
p[j]=a[0][j]/sum[0];
}
for(j=0;j<K;j++){
for(i=1;i<N;i++){
p[j]=p[j]*((a[i][j]+1)/(sum[i]+1))+((1-p[j])*(a[i][j]/(sum[i]+1)));
}
}
for(i=0;i<K;i++)
printf("%f ",p[i]);
}
C++ Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005,M=1e9+7;
int n,k,a[N][N],s[N],b[N];
double ans[N];
int ksm(int x,int y){
int ans=1;
for (;y;y>>=1,x=(ll)x*x%M)
if (y&1)ans=(ll)ans*x%M;
return ans;
}
int main(){
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)scanf("%d",&a[i][j]),s[i]+=a[i][j];
for (int i=1;i<n;i++)b[i]=1;
b[n]=1;double pre=1;
for (int i=n;i;i--){
pre=pre/(s[i]+b[i-1])*b[i];
for (int j=1;j<=k;j++)ans[j]=ans[j]+pre*a[i][j];
}
for (int i=1;i<=n;i++)printf("%.10lf\n",ans[i]);
return 0;
}
Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
String[] S1 = in.readLine().split(" ");
int N = Integer.parseInt(S1[0]);
int K = Integer.parseInt(S1[1]);
int[][]A = new int[N+1][K+1];
int[]B = new int[N+1];
for (int n=1;n<=N;n++) {
String[] S2 = in.readLine().split(" ");
for (int k=1;k<=K;k++) {
A[n][k] = Integer.parseInt(S2[k-1]);
B[n] += A[n][k];
}
if (n>1) B[n]++;
}
StringBuilder S = new StringBuilder("");
for (int k=1;k<=K;k++) {
double P = 0;
for (int n=1;n<=N;n++) {
P = (P + A[n][k])/B[n];
}
S.append(P);
S.append(" ");
}
System.out.println(S);
}
}
Python
def modifyarr(n,k,l,sumi):
dp=[[0 for i in range(k)] for i in range(n)]
for j in range(k):
dp[0][j]=l[0][j]/sumi[0]
for i in range(1,n):
for j in range(k):
dp[i][j]=(dp[i-1][j]*(l[i][j]+1)/(sumi[i]+1))+((1-dp[i-1][j])*(l[i][j]/(sumi[i]+1)))
for i in range(k):
print(dp[n-1][i],end=" ")
print()
l=input().split()
n=int(l[0])
k=int(l[1])
l=[]
sumi=[0 for i in range(n)]
for i in range(n):
lo=input().split()
li=[int(i) for i in lo]
l.append(li)
sumi[i]=sum(li)
modifyarr(n,k,l,sumi)
Q4.
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.
- 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.
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.
C++ Solution
#include<bits/stdc++.h>
using namespace std;
int main ()
{
int num;
cin >> num;
int arr1[num];
for (int i = 0; i < num; i++) cin >> arr1[i];
int M = 1 << 20;
int arr2[M];
char res[M];
for (int i = 1; i < M; i++)
arr2[i] = INT_MAX;
for (int i = 0; i < num; i++)
{
if (arr1[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 (arr2[k] > arr2[k ^ arr1[i]])
arr2[k] = arr2[k ^ arr1[i]] + 1;
else if (arr2[k ^ arr1[i]] > arr2[k])
arr2[k ^ arr1[i]] = arr2[k] + 1;
res[k ^ arr1[i]] = 1;
}
}
int j = M - 1, k = num >> 1;
while (arr2[j] > k)
j--;
cout << j;
return 0;
}
Java
import java.util.*;
class Main
{
public static void main (String[]args)
{
final int N = 120, M = 1 << 20;
int arr2[] = new int[M];
char res[] = new char[M];
Scanner sc = new Scanner (System.in);
int num = sc.nextInt ();
int arr1[] = new int[num];
for (int i = 0; i < num; i++)
arr1[i] = sc.nextInt ();
for (int i = 1; i < M; i++)
arr2[i] = Integer.MAX_VALUE;
for (int i = 0; i < num; ++i)
{
if (arr1[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 (arr2[k] > arr2[k ^ arr1[i]])
arr2[k] = arr2[k ^ arr1[i]] + 1;
else if (arr2[k ^ arr1[i]] > arr2[k])
arr2[k ^ arr1[i]] = arr2[k] + 1;
res[k ^ arr1[i]] = 1;
}
}
int j = M - 1, k = num >> 1;
while (arr2[j] > k)
--j;
System.out.println (j);
}
}
Q5.
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 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.
Sample Input 1
5
15
6
5
12
1
Sample Output 1
2
Explanation:
One possible subsequence is: 5 12
C ++
#include<bits/stdc++.h>
using namespace std;
int Sequence(int arr[], int i, int n, int prev){
if(i == n)
return 0;
int x = Sequence(arr, i + 1, n, prev);
int y = 0;
if (arr[i] > prev)
y = 1 + Sequence(arr, i + 1, n, arr[i]);
return max(y, x);
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0; i< n; i++)
cin>>arr[i];
int res = Sequence(arr, 0, n, 0);
cout<< res;
}
Java
import java.util.Scanner;
class Main
{
public static int Sequence(int[] arr, int i, int n, int prev)
{
if (i == n) {
return 0;
}
int x = Sequence(arr, i + 1, n, prev);
int y = 0;
if (arr[i] > prev) {
y = 1 + Sequence(arr, i + 1, n, arr[i]);
}
return Integer.max(y, x);
}
public static void main(String[] args)
{
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();
}
System.out.print(Sequence(arr, 0, arr.length, Integer.MIN_VALUE));
}
}
Python
def Sequence(arr, i, n, prev=0):
if i == n:
return 0
x = Sequence(arr, i + 1, n, prev)
y = 0
if arr[i] > prev:
y = 1 + Sequence(arr, i + 1, n, arr[i])
return max(y, x)
n = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
print(Sequence(arr, 0, len(arr)))
Q6.
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
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.
CPP
#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;
Java
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);
}
}
Python
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))
Q7.
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].
|
Java
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;
}
}
Python
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))
Q8.
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:
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
|
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.
|
|
3
100
101
100
304
100
1
524
|
2
|
Initial experience level is 100 points.
Defeat the second monster having power of 100 and bonus of 1. Experience level is now 100+1=101.
Defeat the first monster having power of 101 and bonus of 100. Experience level is now 101+100=201.
The third monster can’t be defeated.
|
Java
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);
}
}
Python
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)
CPP
#include<iostream>
#include<map>
using namespace std;
int main(){
int nMon,nExp;
cin>>nMon;
cin>>nExp;
map<int,int> monster;
int arr[nMon],monBon;
for(int i=0; i<nMon; i++){ cin>>arr[i];
}
for(int i=0; i<nMon; i++){ cin>>monBon;
monster[arr[i]]=monBon;
}
map<int,int> :: iterator iter;
int value,valBon,counter=0;;
for(iter=monster.begin(); iter!= monster.end(); iter++){
value=(*iter).first;
valBon=(*iter).second;
if(nExp>=value){
nExp=nExp+valBon;
counter++;
}else{
break;
}
}
cout<<"OUTPUT : "<< counter<<endl;
}
Q9.
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
15
6
5
12
1
|
2
|
One possible subsequence is: 5 12
|
|
6
9
17
2
15
5
2
|
2
|
One possible subsequence is: 2 15
|
|
7
17
16
12
2
8
17
17
|
3
|
One possible subsequence is: 2 8 17
|
CPP
#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;
}
Java
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));
}
}
Python
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)))
Q10.
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.
CPP
#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);
}
Java
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));
}
Python
# 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))
