Join Us
Loading Similar Posts
Entering edit mode
question 2 soltuion
int solution(int U,vector<int> &weight){
int n=weight.size();
int i=0,j=1;//two pointers to check sum of weight of the two car passing bridge
//base case if there is only one car
if(n==1){
if(weight[0]<=U){
return 0;
}
return 1;
}
bool f=true;
//base case if all cars weight greater than U return n
for(int i=0;i<n;i++){
if(weight[i]<=U){
f=false;
break;
}
}
if(f){
return n;
}
int ans=0;
while(j<n){
//as at a time only 2 vehicle can go from bridge
int tot=weight[i]+weight[j];
//check if sum of weight of cars passing is less than or equal to U
if(tot<=U){
i=j;
j++;
}else{
//if tot is more than U than remove the car which has maximum weight out of the two car passing
int v=max(weight[i],weight[j]);
if(v==weight[j]){
j++;
}else{
i=j;
j++;
}
//increament ans by 1
ans++;
}
}
return ans;
}
Entering edit mode
question 01 solution
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
char s[n];
for(int i=0; i<n; i++){
cin>>s[i];
}
int k = 0;
for(int i=0; i<n; i++){
if(s[i] == 'B'){
k++;
}
}
if((2*k) - 1 > n){
cout<<"Not possible"<<endl;
return;
}
int ans = 0;
int cnt = 0;
int i=0, j=0;
while(j<n){
if(j%2 == 0 && s[j] == 'B') cnt++;
if(j-i+1 < 2*k){
j++;
}
else if(j-i+1 == 2*k){
ans = max(ans, cnt);
j = j+2;
if(s[i] == 'B') cnt--;
i = i+2;
}
}
cnt = 0;
while(j<n){
if(j%2 != 0 && s[j] == 'B') cnt++;
if(j-i+1 < 2*k){
j++;
}
else if(j-i+1 == 2*k){
ans = max(ans, cnt);
j = j+2;
if(s[i] == 'B') cnt--;
i = i+2;
}
}
cout<<"the answer is "<<(k-ans)<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
for(int i=0; i<t; i++){
solve();
}
}
Entering edit mode
question 01 solution in cpp
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
char s[n];
for(int i=0; i<n; i++){
cin>>s[i];
}
int k = 0;
for(int i=0; i<n; i++){
if(s[i] == 'B'){
k++;
}
}
if((2*k) - 1 > n){
cout<<"Not possible"<<endl;
return;
}
int ans = 0;
int cnt = 0;
int i=0, j=0;
while(j<n){
if(j%2 == 0 && s[j] == 'B') cnt++;
if(j-i+1 < 2*k){
j++;
}
else if(j-i+1 == 2*k){
ans = max(ans, cnt);
j = j+2;
if(s[i] == 'B') cnt--;
i = i+2;
}
}
cnt = 0;
while(j<n){
if(j%2 != 0 && s[j] == 'B') cnt++;
if(j-i+1 < 2*k){
j++;
}
else if(j-i+1 == 2*k){
ans = max(ans, cnt);
j = j+2;
if(s[i] == 'B') cnt--;
i = i+2;
}
}
cout<<"the answer is "<<(k-ans)<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
for(int i=0; i<t; i++){
solve();
}
}
Has anyone verified the above code , it is showing wrong answers ig, can someone provide correct code