Join Us
Infinite String
Problem
You are given two strings S and T. An infinitely long string is formed in the following manner:
- Take an empty string
- Append S one time.
- Append T two times.
- Append S three times.
- Append T four times.
- and so on, appending the strings alternately and increasing the number of repetitions by 1 each time.
You will also be given an integer K, you need to tell the Kth Character of this infinitely long string.
Samples I/O
Sample Input
- S = "a"
- T = "bc"
- K = 4
Sample Output:
b
Sample Explanation
The string formed will be "abcbcaaabcbcbcbcaaaaa...". So the 4th character is "b".
Constraints
- string s, 1 <= |s| <= 100
- string t, 1 <= |t| <= 100
- long long k, 1 <= k <= 1016
So for given example where S = "a" and T = "bc", here are the blocks respectively
- S-block| "a"
- T-block| "bcbc"
- S-block|"aaa"
- T-block|"bcbcbcbc"
- and so on..
Now lets solve problem in two steps.
Step-I : Find if Kth character falls in either of S-Block or T-Block.
How to find that effeciently? Yes, you guessed it.. binary search! But on what do we apply binary search on?
Lets define a function, F(x) = length of constructed string after adding xth block.
=> F(x) = ceil(x/2) * |S| + floor(x/2) * |T|
Its an easy formula to come up with, try to reason it up as an excercise.
Obviously F(X) is an increasing function, (Why?) and so we can apply binary search on F(X).
We basically want to find out smallest X, such that F(X) >= K.
We can use upperbound version of binary search to find such a X.
Now if the X we get is even then Kth character lies on T-block else it lies on S-block.
Step-II : Finding Kth character
Now that we know if Kth character falls on S or T block, we can easily find required Kth character.
Lets look at simpler problem first.
Say you have an infinite string Z = "bcbcbcbcbcbc....". What is Kth character in it? Since length of repeating string "bc" is 2, answer will simply be Z[K%2].
As we already know X, if we subtract F(X-1) from K then we get a block just like we discussed above.
That gives us, final formula as
S[(K - F(X-1)) % |S|], if Kth character falls in S-block.
or T[(K - F(X-1)) % |T|], if Kth character falls in T-block.
This solves our problem in O(log K) time complexity with O(1) space.
Bonus
We can solve this problem even for bigger constraints! K = 10100000000.
But in this question, you will need to be careful about modulo, class on Elementary Number Theory will be useful.
S, T N, MSo, the string in terms of length parameters looks like this (Blocks of N and M).
NMMNNNMMMMNNNNNMMMMMMNNN......Which can be split into this
NM MN NNMM MMNN NNNMMM MMMNNN..........Which implies, the composite block lengths are,
N+M N+M 2(N+M) 2(N+M) 3(N+M) 3(N+M).......
2(N+M) 4(N+M) 6(N+M)........From here follows a pretty standard binary search solution. I guess there's some issue with the markdown.. @Admin User-1
Neat observation @vaibhavr . I think this is an alternative solution?
Posted solution doesn't require any creativity like you employeed.
In posted solution after getting F(x) = ceil(x/2) * |S| + floor(x/2) * |T|, which is clearly an increasing function we can directly bseasrch on F(x) w/o making any further observation.
Yes, we have disabled markdown temporarily to support html..
so you can use usual html tags like <\blockquote> <\b>, <\i>, <\p> etc.
#include<bits/stdc++.h>
using namespace std;
long long int f(long long int x, int m, int n)
{
long long int length=(((x+1)/2)*((x+1)/2))*m+((x/2)*(x/2+1))*n;
return length;
}
bool isGood(long long int x, long long int k, int m, int n)
{
long long int length=f(x, m, n);
if(length>=k)
return true;
return false;
}
int main()
{
string s,t;
cin>>s>>t;
int m=s.length();
int n=t.length();
long long int k;
cin>>k;
int lo=1, hi=1e8;
while(lo<hi)
{
int mid=lo+(hi-lo)/2;
if(isGood(mid, k, m, n))
{
hi=mid;
}
else
lo=mid+1;
//lo tells on which string i need to do work
}
int length2=k-f(lo-1, m, n);
length2--;
char ans;
if(lo%2)
{
ans=s[(length2)%m];
}
else
{
ans=t[(length2)%n];
}
cout<<ans;
}
