The solution given by the editor, is also O(N^2) only na…, how is it O(9N), or O(N)?
what I understood from the editor has given as the solution as:
for(int i=1;i<N;i++)
{
for(int j=i+1;j<min(i+9,N);j++)
{
…comparision condition…
}
}
Now, as i itself starts from 1, so min(i+9,N) will always be N…
So, even the editorial solution is O(N^2)…, how it is O(9N) or O(N)?
Please explain…
thanks man, this is exactly what i was seeking
it is of O(9.N) in worst case as in second loop j is traversing upto min(i+9 , N) in which when you will take a big constraints it will give O(9.N) which is also equivalent to O(N).
You can also say that the second loop will only run for 9 times at worst.
Go and check out my HASH MAP solution with a logic that j-i=|Sj-Si| will result into either
j-i = Sj-Si or i-j = Sj-Si.
this will result into either Sj-j = Si-i or Sj+j = Si+i.
hence we will store occurences of Si-i and Sj-j for every 1 <= i <= N.
Clean solution that works for arbitrary sequences (doesn’t rely on the digits being values from 0-9):
for (int step = 0; step < 2; step++) {
map<int, int> freq;
for (int i = 0; i < n; i++)
freq[a[i] - i]++;
for (auto [k, v] : freq)
ans += nc2(v);
reverse(all(a));
}
@m0nk3yd1u55y I am still not getting that how will it be O(9N)…
The solution given by the editor, is also O(N^2) only na…, how is it O(9N), or O(N)?
what I understood from the editor has given as the solution as:
for(int i=1;i<N;i++)
{
for(int j=i+1;j<min(i+9,N);j++)
{
…comparision condition…
}
}
Lets analyze:
Now, as i itself starts from 1, so min(i+9,N) will be as follows…
min(1+9,N)=10–>loop j runs 10 times.
min(2+9,N)=11–>loop j runs 11 times.
min(3+9,N)=12–>loop j runs 12 times.
min(4+9,N)=13–>loop j runs 13 times.
…continuing…
min(N-9+9,N)=N–>loop j runs N times.
min(N-8+9,N)–>loop j runs N times.
min(N-7+9,N)–>loop j runs N times.
…till min(N+9,N)–>where loop j runs N times.
So how is it that, loop j will run at “most 9” times?
Please explain…
@anyone?
PS: I haven’t really done with the hash map, so I am not commenting on the solution given by other guys. As soon as I will complete it, I will revisit the solution of hash map as well.
Here’s a similar approach but with a break statement and nested for loops.
// Don't Just copy the code, Understand it first.
// -- theskyspace(Insta profile also) ;)
#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x,y) cout << #x << " = " << x << " , " << #y << " = " << y << endl;
typedef long long ll;
typedef pair<int , int> pairs;
ll M = 10e8 + 7;
void solve(){
// Let's start
ll n;
string s;
ll count = 0;
cin >> n >> s;
for (int i = 0; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
if (j-i > 9)
{
break;
}
if(j-i == abs(s[j] - s[i])){
count++;
}
}
}
cout << count << endl;
}
//Driver's code
int main(){
// Stdin and stdout.
ios::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
https://www.codechef.com/viewsolution/52354450
can anyone help me with this code I’m not able to find why it is giving WA what is flaw in the logic?
it is like that it max to max run to 9 elements further because after that difference between i and j is always greater than 9 and we can never obtain the required solution therefore no need of running it N^2 times :)…
@prit_esh_07 Yeah, I got the thing that diff of j-i is max 9.
But in order to travel the whole string, i.e, upto the size of the string(or we can say the last element of the string…), it is basically N–>size of the string. I am talking abt inner loop , or loop j btw…
@ajit123q could you explain the solution which you have given…, sorry but I still fail to understand that how will the j loop, min(i+9,N) will not be O(N)…
or anyone plz?
the thing is that u dont’t have to traverse j to whole N u have to ensure condition upto 9 elements ahead for every i just think in that manner .
bro can u explain this part
Thanks!
yeah sure !
That is a simplification of nC2 , where n is the number of occurrences of a value X. we just need to find how many pairs can be made with X number of options.
so, nC2 translates to
n!/((2!)*((n-2)!))
which on solving further gives : n(n-1)/2*
Hope it is was a clear explanation for answering your question.
Mine approach
, so yeah, no issues now!#define NDEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pi = pair<int, int>;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define eb emplace_back
#define sz(x) (int)(x).size()
#define ins insert
#define MOD 1000000007t
#define endl '\n'
#define all(x) begin(x), end(x)
#define desc greater<int>()
#define rall(x) rbegin(x), rend(x)
#define error 1e-6
#define rep(i, a, b) for(__typeof(b) i=(a-(a>b));i!=(b-(a>b));i+=(1-2*(a>b)))
#define repa(x, a) for(auto x: a)
#define repr(x, a) for(auto &x: a)
#define prec(n) cout << fixed << setprecision(n)
#define what_is(x) cout << #x << " = " << x << endl
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, -1, 0, 1 };
// g++ test.cpp -o test && ./test < input.txt
void solve() {
int n; cin >> n;
string s; cin >> s;
int ans = 0;
rep(d, 1, 10) {
for(int i=0; i<n-d; i++) {
if(d == abs(s[i] - s[i+d])) ans++;
}
}
cout << ans << endl;
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
int tc = 1; cin >> tc;
while(tc--) solve();
return 0;
}
Buddy Look at the starting point of j it goes from I+1 to MIN( I+9, N )
How can It will be N*N. when we are going to at most i+9 for every i.