Problem link: CodeChef: Practical coding for everyone
Approach: Used binary search on the index at which the number of operations are counted.
Could anyone please tell me which test case was I missing?
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
bool check(string str, int val, int k){
int cnt =0, i;
for(i=val;i>=0;i--){
if(str[i] == '0'){
continue;
}
int num = str[i] - '0';
num = num + cnt%10;
num = num%10;
str[i] = '0' + num;
cnt = cnt + 10 - (str[i] - '0');
}
if(cnt > k){
return false;
}
return true;
}
int main(){
int t;
cin>>t;
while(t--){
int n, k, i ,j;
cin >>n >> k;
string str;
cin>>str;
int left = 0, right = n-1, mid = left + (right - left)/2;
if(n==1){
int num = str[0]-'0';
if(10 - num <= k ){
cout<<"1"<<endl;
}
else{
cout<<"0"<<endl;
}
}
else if(n ==2){
int num1 = 10 - str[0]+ '0';
int num2 = 10 - str[1] + '0';
int count = 0;
while(num1 + 10 <= k){
num1 = num1 +10;
}
while(num2 + 10 <= num1){
num2 = num2 +10;
}
if(num1 > k){
cout<<"0"<<endl;
}
else if(num1>=num2){
cout<<"2"<<endl;
}
else{
cout<<"1"<<endl;
}
}else{
while(right - left > 1){
mid = left + (right - left)/2;
if(check(str,mid,k)){
left = mid;
}
else{
right = mid -1;
}
}
if(!check(str, 0, k)){ // checking if no index can be made zero
int f, c =0 ;// the initial zeros already present in given string
for(f=0;f<n;f++){
if(str[f] != '0'){
break;
}else{
c++;
}
}
cout<<c<<endl;
}
else if(check(str, right, k)){
cout<<right + 1<<endl;
}
else{
cout<<left + 1<<endl;
}
}
}
}
Please help!