Can anybody help in one of the hackerearth codemonk question “Cyclic Shift”.
link : Code Monk - Be a better programmer
please check the 3rd question. I got time limit error in two test cases. i need some help to solve it in O(nlogn) or O(n) time if it is possible.
2 Likes
Hey i have optimized it, but getting WA verdict on 3 testcases, AC on others.
Can u share ur approach ?
using namespace std;
int num(string s){
long long int i,sum=0,p;
p=stoi(s);
i=0;
while(p>0){
int t=p%10;
p=p/10;
int temp=pow(2,i);
sum+=t*temp;
i++;
}
return sum;
}
string shift(string s,int n){
int i;
char temp;
for(i=0;i<n-1;i++){
temp=s[i];
s[i]=s[i+1];
s[i+1]=temp;
}
return s;
}
int main() {
// #ifndef ONLINE_JUDGE
// // for getting input from input.txt
// freopen(“input.txt”, “r”, stdin);
// // for writing output to output.txt
// freopen(“output.txt”, “w”, stdout);
// #endif
int t;
cin>>t;
while(t–){
string s;
long long int n,max=0,i,k,count=0;
cin>>n>>k>>s;
// s=shift(s,n);
// cout<<s<<"\n"<<num(s)<<endl;
for(i=1;i<=n;i++){
s=shift(s,n);
if(num(s)>max){
max=num(s);
count=i;
}
}
cout<<k*(count)+1<<endl;
}
return 0;
}
**My output is fine but submission shows runtime error…please drop in any better solutions **
It is throwing a runtime error because your stoi function gets out of range for n > 32
can u correct it?
Help Me, to find some possible optimization so that my code get AC??
my Code
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef long long ll;
void solve(){
ll n;cin>>n;
ll b;cin>>b;
string str; cin>>str;
deque<bool> dq;
for(ll i=0;i<n;i++){
if(str[i]=='1')dq.push_back(true);
else dq.push_back(false);
}
str = "";
set<deque<bool>> s;
s.insert(dq);
for(ll i=1;i<=n;i++){
bool c = dq.front(); dq.pop_front();
dq.push_back(c);
s.insert(dq);
}
deque<bool> ans = *s.rbegin();
s.clear();
map<deque<bool>,vector<int>> mp;
mp[dq].push_back(0);
for(ll i=1;i<=n-1;i++){
bool c = dq.front(); dq.pop_front();
dq.push_back(c);
mp[dq].push_back(i);
}
ll out = 0;
vector<int> vec = mp[ans];
ll cnt = vec.size();
if(cnt>=b){
cout << vec[b-1];
}else{
if(b%cnt==0){
out = (b/cnt - 1)*(n);
b-=((b/cnt - 1)*(cnt));
}else{
out = (b/cnt)*(n);
b-=((b/cnt)*(cnt));
}
if(b>0){
b--;
out+=(vec[b]);
}
cout << out;
}
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
cout.precision(20);
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
int T=1; cin>>T;
while(T--){
solve();
if(T)cout << endl;
}
return 0;
}
#input4 → input-4
#input 5 → input 5
#include
using namespace std;
int main()
{
int t;
cin >> t;
while (t)
{
int n, k;
cin >> n >> k;
string strA, a, pre, strB, comp;
cin >> strA;
a = strA;
pre = strA;
strB = strA;
char ch;
long unsigned int i = 0, sum = 0, count = 0, c = 0;
while (1)
{
if (i == 0)
ch = strA[i];
if (i < n - 1)
strA[i] = strA[i + 1];
if (i == n - 1)
strA[i] = ch;
if (i == n)
{
comp = strB;
c++;
if (pre > strA && strB < pre)
{
strB = pre;
}
else if (strA > pre && strB < strA)
{
strB = strA;
}
if (strB != comp)
count = 0;
if (strB == comp && strB > strA)
count++;
pre = strA;
i = -1;
if (strA == a)
{
break;
}
}
i++;
}
k = k - 1;
count = c - count;
if (count == 1 && strB == pre)
count = 0;
sum = k * c + count;
cout << sum << endl;
t--;
}
}