1. CODESMASH 2.
Minbin - [20 Marks]
Minbin has an integer array A of size N. She wants to minimize all the elements in
the array equal to the smallest possible integer value. She can do so, by selecting
any two adjacent elements of array A, say index i and (i+1). Then set the values of
A[i] and A[i+1] as:
A[i] = A[i+1] = A[i] & A[i+1]
She can perform this operation any number of times, to get the smallest possible
integer value, say X. Your task is to help Minbin find and return the smallest
positive integer value of P representing 2P to be greater than or equal to X (2P >=
X).
Note:
'&' in the operation denotes bitwise AND operation.
The value of P will always be greater than 0.
Assume 1 based indexing.
Constraints:
1 < N < 1000
0 ≤ values of elements in array ≤ 109+7
Input Specification:
input1 : An integer value N, representing the size of the array A.
input2 : An integer array A.
Output Specification:
Return the smallest positive integer value P representing 2P to be greater than
equal to X (2P >= X).
Example 1:
input1 : 2
input2 : {2,4}
Output : 1
Explanation:
Here, we have two elements in array A as {2,4}. So, we can apply the operation on
i=1
A[1] = A[1] & A[2] = 2 & 4 = 0
A[2] = A[1] & A[2] = 2 & 4 = 0
The modified array A is {0,0}, with all the elements equal to the smallest possible
integer value which is 0. Here, 21 > 0, therefore 1 is the value of P at which the
elements of the array are minimum, Hence, 1 is returned as the output.
Example 2:
input1 : 4
input2 : {3,7,11,3}
Output : 2
Explanation:
Here, we have four elements in array A as {3,7,11,3}. So, we can get the smallest
possible integer value in two ways:
1st Way:
First apply the operation on i=1 as
A[1] = A[1] & A[2] = 3 & 7 = 3
A[2] = A[1] & A[2] = 3 & 7 = 3
Then apply the operation on i=3 as
A[3] = A[3] & A[4] = 11 & 3 = 3
A[4] = A[3] & A[4] = 11 & 3 = 3
2nd Way:
Apply the operation on i=2 as
A[2] = A[2] & A[3] = 7 & 11 = 3
A[3] = A[2] & A[3] = 7 & 11 = 3
The modified array A is {3,3,3,3}, with all the elements equal to the smallest
possible integer value which is 3. Here, 22 > 3, therefore 2 is the value of P at
which the elements of the array are minimum. Hence, 2 is returned as the output.
CODE
import java.util.*;
class UserMainCode {
public static int minBin(int input1, int[] input2) {
// Step 1: Calculate the bitwise AND of all elements in the array
int X = input2[0];
for (int i = 1; i < input1; i++) {
X &= input2[i];
}
// Step 2: Find the smallest P such that 2^P >= X
int power = 0;
int val = 1;
while (val < X) {
val *= 2;
power++;
}
return power;
}
}
all testcase passed
2ND QUESTION
Christmas Gifts - [30 Marks]
It is Christmas Eve; Stanley and his friends have decided to play a game. There are
N friends (including Stanley) standing in a horizontal line, shoulder to shoulder.
Each friend will toss a coin. On getting Heads, that friend will give one gift to
each friend standing left of him and on getting Tails, that friend will give one
gift to each friend standing right of him.
A string S holds a result of toss for each friend. You can swap two adjacent toss
results at most once so that everyone standing in the line receives a gift.
Your task is to find and return an integer value representing the minimum index
value at which the swapping operation is performed. If the swap operation is not
required, then return 0 and even after performing the swap the above condition is
not met then return -1.
Note:
Take H for heads and T for tails.
Assume 1-based indexing.
Constraints:
1 < N < 60000
Input Specification:
input1 : An integer value N denoting the size of the string S.
input2 : A string S consisting of only letters ‘H' and ‘T' denoting the result of
coin toss for each student.
Output Specification:
Return an integer value representing the minimum index value at which the swapping
operation is performed. If the above-mentioned conditions are not met then return 0
or -1, accordingly.
Example 1:
input1 : 2
input2 : HT
Output : 1
Explanation:
Here the string S is HT which means there are two friends.
We can see that none of the friends is getting any gift as the first friend would
pass on the gift to the person on his left and the second friend would pass on the
gift to the person on his right. So, we can perform one swap operation at index 1
to get a new string TH.
Now both friends will receive exactly one gift, satisfying the above-mentioned
condition. Hence, 1 is returned as the output.
Example 2:
input1 : 2
input2 : HH
Output : -1
Explanation:
Here the string S is HH which means there are two friends.
We can see that the friend at index 2 will never be able to receive any gifts even
if we perform the swapping operation as it would result in the same string. Hence,
-1 is returned as the output.
code is not passing all the test cases
3rd question
Thanksgiving - [50 Marks]
In an event of Thanksgiving there is a feast organized for guests. The quantity of
cake distributed among N guests is stored in an array plates. However, on the day
of the feast additional guests arrived and the manager now has no other way but to
reduce the quantity of cakes from these plates. He wants to save at least M
kilograms of cake for the extra guests that came in, but wants to reduce the
quantity of cake only from those plates which have more than or equal to K
kilograms of cake.
Your task is to help the manager to find and return an integer value representing
the maximum value of K, he can maintain after saving at least M kilograms of cake.
Constraints:
1 < N < 100
0 ≤ M ≤ 109+7
0 ≤ values of elements in array ≤ 109+7
Input Specification:
input1 : An integer value N, representing the number of guests.
input2 : An integer value M, representing the minimum kilograms of cake that needs
to be saved.
input3 : An integer array plates, where each element represents quantity of cake in
each guest's plate.
Output Specification:
Return an integer value representing the maximum value of K after saving M
kilograms of cake.
Example 1:
input1 : 4
input2 : 5
input3 : {4,8,7,1}
Output : 5
Explanation:
K can be any value starting from 1. In this example, maximum value of K will be 5
that will help in saving at least M = 5 kilograms of cake for the guests. So, you
can reduce the quantity of cakes in the following manner:
From the plate of the second guest, you can reduce the cake by 3 kilograms, which
leaves the second guest with 5 kilograms of cake, which is equal to K.
Similarly, from the plate of third guest, you can reduce the cake by 2 kilograms,
which leaves the second guest with 5 kilograms of cake, which is equal to K.
So the final plates array will be {4,5,5,1}. Hence, 5 is returned as output.
Example 2:
input1 : 5
input2 : 7
input3 : {10,11,13,5,6}
Output : 9
Explanation:
In this example, maximum value of K will be 9 that will help in saving at least M =
7 kilograms of cake for the guests. So, you can reduce the quantity of cakes in the
following manner:
From the plate of the first guest, you can reduce the cake by 1 kilogram, which
leaves the first guest with 9 kilograms of cake, which is equal to K.
Next, from the plate of the second guest, you can reduce the cake by 2 kilograms,
which leaves the second guest with 9 kilograms of cake, which is equal to K.
Similarly, from the plate of the third guest, you can reduce the cake by 4
kilograms, which leaves the third guest with 9 kilograms of cake, which is equal to
K.
So the final plates array will be {9,9,9,5,6}. Hence, 9 is returned as output.
the final code is
#include <stdio.h>
#include <algorithm> // This is necessary for sort
using namespace std;
int thanksgiving(int input1, int input2, int input3[]) {
int N = input1;
int M = input2;
int* plates = input3;
// Sort the plates array
sort(plates, plates + N);
// Special case when M == 0
if (M == 0) {
return plates[N - 1]; // Return the maximum value in plates
}
// Set binary search boundaries
int left = 0;
int right = 1e9 + 7; // Maximum possible value of K based on the constraints
while (left < right) {
int mid = left + (right - left + 1) / 2;
long long sum = 0;
// Calculate how much cake we can save by reducing plates to 'mid'
for (int i = N - 1; i >= 0 && plates[i] >= mid; i--) {
sum += plates[i] - mid;
if (sum >= M) break; // No need to continue if we've saved enough
}
// If we can save enough cake, search for a larger K
if (sum >= M) {
left = mid;
} else {
right = mid - 1; // Otherwise, search for a smaller K
}
}
return left; // The maximum value of K that satisfies the condition
}
All Testcase Passed
4.Max OR Array
Jonathan is utilizing his summer vacations learning about arrays. He is solving a
problem and gets stuck at some point so he asks you for help.
You are given an array A of size N containing non-negative integers. You can remove
a subarray from array A, such that the bitwise OR of all the elements in the
remaining array is the maximum possible.
Your task is to find and return an integer value the size of the maximum length
subarray that can be removed.
Input Specification:
input1 : An integer array A
input2 : An integer N denoting the size of the array
Output Specification:
Return an integer value the size of the maximum length subarray that can be
removed.
Example 1:
input1 : {1,4,24,2}
input2 : 4
Output : 0
Explanation:
The bitwise OR of the whole array is 31 which is the maximum value possible and it
cannot be achieved by removing any subarray. Hence, 0 is returned as the output.
Example 2:
input1 : {2,1,1,5,4,4,8,1}
input2 : 8
Output : 4
Explanation:
The maximum length subarray that can be removed is {1,1,5,4}. The bitwise OR of the
remaining elements of array {2,4,8,1} is 15 which is the maximum value possible.
Hence, 15 is returned as the output.
Code is
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int MaxORArray(int* input1, int input2) {
int ans=0;
int count[32]={0};
for(int i=0;i<input2;i++)
{
for(int j=0;j<32;j++)
{
if((input1[i]>>j)&1)
count[j]++;
}
}
for(int l=0,r=0;r<input2;r++)
{
int cnt=0;
for(int j=0;j<32;j++)
{
if((input1[r]>>j)&1)
{
count[j]--;
if(count[j]==0)
cnt++;
}
}
while(cnt)
{
for(int j=0;j<32;j++)
{
if((input1[l]>>j)&1)
{
if(count[j]==0)
cnt--;
count[j]++;
}
}
l++;
}
ans=max(ans,r-l+1);
}
return ans;
}
All Testcase Passed
