# SQRDSUB - Editorial

**URL:** <https://discuss.codechef.com/t/sqrdsub-editorial/61193>\
**Category:** editorial\
**Tags:** easy, editorial, pointers, taran\_1407, april20\
**Created:** [April 10, 2020, 12:49am UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193 "2020-04-10T00:49:06Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![taran\_1407](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taran_1407/32/299985_2.png) [@taran\_1407](https://discuss.codechef.com/u/taran_1407)\
**Post date:** [April 10, 2020, 12:49am UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/1 "2020-04-10T00:49:06Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/SQRDSUB)  
[Contest: Division 1](https://www.codechef.com/APRIL20A/problems/SQRDSUB)  
[Contest: Division 2](https://www.codechef.com/APRIL20B/problems/SQRDSUB)

**Setter:** [Raj Khandor](https://www.codechef.com/users/hackslash_123)  
**Tester:** [Felipe Mota](https://www.codechef.com/users/fmota)  
**Editorialist:** [Taranpreet Singh](https://www.codechef.com/users/taran_1407)

# DIFFICULTY:

Easy

# PREREQUISITES:

Basic Math, Pointers.

# PROBLEM:

Given an array A of length N, find the number of good contiguous subsequences of A where a contiguous subsequence is considered good if the product of values can be written as the difference of two perfect squares.

# QUICK EXPLANATION

- A number can be written as the difference of two perfect squares if and only if it is odd, or a multiple of 4.
- We just need to find the number of contiguous subsequences having the product as multiple of 2 but not multiple of 4, and subtract from the total number of contiguous subsequences.
- If we replace odd values with zeroes, multiples of 4 with 2 and rest with 1, the number of contiguous subsequences to be subtracted is the number of contiguous subsequences with sum 1, which can be easily computed using pointers.

# EXPLANATION

As explained in detail [here](https://nrich.maths.org/whatspossible/solution), any number can be written as the difference of two perfect squares if either one of the following holds.

- The number is odd.
- The number is a multiple of 4.

Conversely, the only numbers which cannot be written as the difference of perfect squares are of the form 2\*p for some odd number p. We just need to count the number of subarrays, which have the product of this form.

Another thing we can notice is that only the power of 2 in product matters, so we can replace each A\_i by the exponent of 2 in A\_i. In this reduced array, we need to count the number of subarrays with sum exactly 1 and subtract from total number of subarrays.

Now, this is a well-known problem, as explained [here](https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/), and in [this](https://codeforces.com/blog/entry/65028?#comment-490191) comment.

Briefly stating, we can compute prefix sums and then for each fixed right end, if the current sum is X, we find the number of positions with sum X-1 which can be found easily using a map. It can also be found using pointers since the array values are non-negative (refer tester’s solution for this).

# TIME COMPLEXITY

The time complexity is O(N) or O(N\*log(N)) per test case depending upon implementation.

# SOLUTIONS:

> **Setter's Solution**
>
> ```
> #include <bits/stdc++.h>
> using namespace std;
> typedef long long ll;
> int main()
> {
> ios_base::sync_with_stdio(false);
> cin.tie(NULL);
> ll t;
> cin>>t;
> while(t--)
> {
> ll n;
> cin>>n;
> ll a[n];
> for(ll i=0;i<n;i++)
> cin>>a[i];
> 
> ll b[n];
> for(ll i=0;i<n;i++)
> {
> if(a[i]%4 == 0)
> b[i] = 2;
> else if(a[i]%2 == 0)
> b[i] = 1;
> else
> b[i] = 0;
> }
> ll pre[n];
> pre[0] = b[0];
> for(ll i=1;i<n;i++)
> pre[i] = pre[i-1] + b[i];
> 
> ll ans=0;
> for(ll i=0;i<n;i++)
> {
> if(b[i] == 0)
> {
> ll idx=upper_bound(pre,pre+n,pre[i])-pre;
> ans += idx-i;
> 
> idx=lower_bound(pre,pre+n,pre[i]+2)-pre;
> ans += n-idx;
> }
> else if(b[i] == 1)
> {
> ll idx=lower_bound(pre,pre+n,pre[i]+1)-pre;
> ans += n-idx;
> }
> else
> {
> ans += n-i;
> }
> }
> cout<<ans<<"\n";
> }
> return 0;
> }
> 
> ```

[details = “Tester’s Solution”]  
#include \<bits/stdc++.h\>  
using namespace std;  
template vector create(size\_t n){ return vector(n); }  
template\<typename T, typename… Args\> auto create(size\_t n, Args… args){ return vector\<decltype(create(args…))\>(n, create(args…)); }  
int main(){  
ios::sync\_with\_stdio(false);  
cin.tie(0);  
/\*\*  
(p^2 - q^2) = (p + q) \* (p - q) = A \* B

```
	We can derive that A and B have the same parity,
	so the array interval can be represented if the 
	interval product is either odd or divisible by 4,
	this can be calculated by knowing the number of 2
	in some interval.
	 
	We can use two pointers and accumulated sum to
	calculate the number of intervals in O(N)
	 * */
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		vector<int> a(n + 1, 0);
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			a[i] = abs(a[i]);
			int r = 0;
			while(a[i] % 2 == 0 && r < 2) r++, a[i] /= 2;
			a[i] = r;
		}
		for(int i = 0; i < n; i++) a[i + 1] += a[i];
		int p0 = 0, p1 = 0;
		long long ans = 0;
		for(int i = 1; i <= n; i++){
			while(p0 < i && a[i] - a[p0] >= 2) p0++;
		   	while(p1 < i && a[i] - a[p1] >= 1) p1++;
			ans += i - (p1 - p0);
		}
		cout << ans << '\n';
	}
	return 0;
}

```

[/details]  
[details = “Editorialist’s Solution”]  
import java.util._;  
import [java.io](http://java.io)._;  
import java.text._;  
class SQRDSUB{  
//SOLUTION BEGIN  
void pre() throws Exception{}  
void solve(int TC) throws Exception{  
int n = ni();  
int[] A = new int[n];  
for(int i = 0; i\< n; i++)A[i] = ni();  
int[] B = new int[n];//B[i] == 2 if a[i] == 0, B[i] = 0 if a[i]%4 == 0, 1, 3, B[i] = 1 if a[i]%4 == 2  
long total = (n_(long)n+n)/2;  
for(int i = 0; i\< n; i++){  
if(A[i]%4 == 0)B[i] = 2;  
else if(A[i]%2 == 0)B[i] = 1;  
else B[i] = 0;  
}  
//We need to subtract number of subarrays with sum 1 now  
int prefSum = new int[3\*n];  
prefSum[0]++;  
int sum = 0;  
for(int i = 0; i\< n; i++){  
sum += B[i];  
if(sum \> 0)total -= prefSum[sum-1];  
prefSum[sum]++;  
}  
pn(total);  
}  
//SOLUTION END  
void hold(boolean b)throws Exception{if(!b)throw new Exception(“Hold right there, Sparky!”);}  
DecimalFormat df = new DecimalFormat(“0.00000000000”);  
static boolean multipleTC = true;  
FastReader in;PrintWriter out;  
void run() throws Exception{  
in = new FastReader();  
out = new PrintWriter(System.out);  
//Solution Credits: Taranpreet Singh  
int T = (multipleTC)?ni():1;  
pre();for(int t = 1; t\<= T; t++)solve(t);  
out.flush();  
out.close();  
}  
public static void main(String args) throws Exception{  
new SQRDSUB().run();  
}  
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}  
void p(Object o){out.print(o);}  
void pn(Object o){out.println(o);}  
void pni(Object o){out.println(o);out.flush();}  
String n()throws Exception{return in.next();}  
String nln()throws Exception{return in.nextLine();}  
int ni()throws Exception{return Integer.parseInt(in.next());}  
long nl()throws Exception{return Long.parseLong(in.next());}  
double nd()throws Exception{return Double.parseDouble(in.next());}

```
	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

```

[/details]

Feel free to share your approach. Suggestions are welcomed as always. 🙂

---

<div class="post-metadata">

**Author:** ![anon93552178](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon93552178](https://discuss.codechef.com/u/anon93552178)\
**Post date:** [April 13, 2020, 10:41am UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/2 "2020-04-13T10:41:44Z")

</div>

[Here](https://github.com/Just-A-Visitor/Algorithmic-Pseudocode/blob/master/Codechef/Dynamic%20Programming/Squared%20Subsequences%20(SQRDSUB)/Editorial.pdf) is my alternate (and somewhat easy) version of the proof about the properties of numbers which can be written as difference of 2 squares (and a simple DP [implementation](https://github.com/Just-A-Visitor/Algorithmic-Pseudocode/blob/master/Codechef/Dynamic%20Programming/Squared%20Subsequences%20(SQRDSUB)/DP_Approach.cpp))

---

<div class="post-metadata">

**Author:** ![ssrivastava990](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ssrivastava990/32/216836_2.png) [@ssrivastava990](https://discuss.codechef.com/u/ssrivastava990)\
**Post date:** [April 13, 2020, 10:49am UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/3 "2020-04-13T10:49:26Z")

</div>

> **[Ideone.com](https://ideone.com/f2f4Dx)**
>
> Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

1. Convert to mod 4 array

2. For each ‘2’ or ‘-2’ count total continous odd element in left (let it be x ) and continous odd element in right (let it be y)

3. multiply (x+1) \* (y+1)  
4.summation all

4. subtract it from total subarrays ie., (n\*(n+1)/2)

---

<div class="post-metadata">

**Author:** ![ssrivastava990](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ssrivastava990/32/216836_2.png) [@ssrivastava990](https://discuss.codechef.com/u/ssrivastava990)\
**Post date:** [April 13, 2020, 11:04am UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/5 "2020-04-13T11:04:23Z")

</div>

link broken

---

<div class="post-metadata">

**Author:** ![arin0](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arin0/32/28512_2.png) [@arin0](https://discuss.codechef.com/u/arin0)\
**Post date:** [April 13, 2020, 11:08am UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/6 "2020-04-13T11:08:08Z")

</div>

Right now codechef is not allowing one to see others submissions. 😐

---

<div class="post-metadata">

**Author:** ![ishita\_gupta](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ishita_gupta/32/3653_2.png) [@ishita\_gupta](https://discuss.codechef.com/u/ishita_gupta)\
**Post date:** [April 13, 2020, 12:16pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/7 "2020-04-13T12:16:02Z")

</div>

Detailed solution of April Long Challenge.

> **[CodeChef April Long Challenge Solution (Div 2)](https://medium.com/@manthangupta109/codechef-april-long-challenge-solution-div-2-cc0b05c9cbfe)**
>
> Overly Simplified

---

<div class="post-metadata">

**Author:** ![nvdrag\_123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nvdrag_123/32/3653_2.png) [@nvdrag\_123](https://discuss.codechef.com/u/nvdrag_123)\
**Post date:** [April 13, 2020, 12:23pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/8 "2020-04-13T12:23:16Z")

</div>

The better and most easiest way to see this problem is put numbers divisible by 4 = 2, else if they are odd put them 0 else put them 1. and find number of subarrays with sum = 1, and substract them from total subarrays. then the question is standard prefix sum problem.  
[my submission for reference](https://www.codechef.com/viewsolution/31829055)

---

<div class="post-metadata">

**Author:** ![anon40875119](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon40875119](https://discuss.codechef.com/u/anon40875119)\
**Post date:** [April 13, 2020, 12:44pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/9 "2020-04-13T12:44:12Z")

</div>

Since the sum of **N** over all test cases doesn’t exceed 10^6, I am not able to figure out why my code got TLE for original constraints even though it’s **O(N x Log(N))**

Code: [ideone](https://ideone.com/fnzvBG)

If I made any mistake then please point it out. Thanks! 🙂

---

<div class="post-metadata">

**Author:** ![jay\_ponkia](https://discuss.codechef.com/user_avatar/discuss.codechef.com/jay_ponkia/32/208155_2.png) [@jay\_ponkia](https://discuss.codechef.com/u/jay_ponkia)\
**Post date:** [April 13, 2020, 12:50pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/10 "2020-04-13T12:50:42Z")

</div>

Hello,

Can you tell me what is wrong with my solution here?

I have counted odd values on the left side and right side of 2. and after that I have done this ans += total - (left + 1) \* (right + 1).

What is wrong here?

```
#include <bits/stdc++.h>

#define int long long int
#define endl "\n"

using namespace std;

int solve(int arr[], int n)
{
	//int arr[12] = {1, 1, 1, 1, 2, 2, 1, 1, 1, 4, 2, 2};
	//int dpL[12] = {1, 2, 3, 4, 4, 0, 1, 2, 3, 0, 0, 0};
	//int dpR[12] = {4, 3, 2, 1, 0, 3, 3, 2, 1, 0, 0, 0};
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] % 4 == 0)
			arr[i] = 4;
		else if (arr[i] % 2 == 0)
			arr[i] = 2;
		else if (arr[i] % 2 == 1)
			arr[i] = 1;
	}
	
	/*Conditions for dpL*/
	int dpL[n] = { 0 };
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			if (arr[i] == 1) {
				dpL[i] = 1;
			} else if (arr[i] == 2 || arr[i] == 4) {
				dpL[i] = 0;
			}
		} else {
			if (arr[i] == 1) {
				dpL[i] = dpL[i - 1] + 1;
			} else if (arr[i] == 2) {
				if (arr[i - 1] == 1) {
					dpL[i] = dpL[i - 1];
				} else if (arr[i - 1] == 2 || arr[i - 1] == 4) {
					dpL[i] = 0;
				}
			} else if (dpL[i] == 4) {
				dpL[i] = 0;
			}
		}
	}
	
	/*Conditions for dpR*/
	int dpR[n] = { 0 };
	for (int i = n - 1; i >= 0; i--) {
		if (i == (n - 1)) {
			if (arr[i] == 1) {
				dpR[i] = 1;
			} else if (arr[i] == 2 || arr[i] == 4) {
				dpR[i] = 0;
			}
		} else {
			if (arr[i] == 1) {
				dpR[i] = dpR[i + 1] + 1;
			} else if (arr[i] == 2) {
				if (arr[i + 1] == 1) {
					dpR[i] = dpR[i + 1];
				} else if (arr[i + 1] == 2 || arr[i + 1] == 4) {
					dpR[i] = 0;
				}
			} else if (dpR[i] == 4) {
				dpR[i] = 0;
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
	 	if (arr[i] == 2) {
			sum += (dpL[i] + 1) * (dpR[i] + 1);
		}
	}
	
	return sum;
}

int32_t main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		int total = (n * (n + 1)) / 2;
		
		cin >> n;
		
		int arr[n];
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			arr[i] = abs(arr[i]);
		}
		int ans = solve(arr, n);
		cout << total - ans << endl;
	}
}
```

---

<div class="post-metadata">

**Author:** ![striker22](https://discuss.codechef.com/user_avatar/discuss.codechef.com/striker22/32/123420_2.png) [@striker22](https://discuss.codechef.com/u/striker22)\
**Post date:** [April 13, 2020, 2:03pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/11 "2020-04-13T14:03:20Z")

</div>

@taran_1407 An elegant and very simple proof of an odd number can be expressed as a difference of perfect square i.e. p^{2} - q^{2}:

**Step-1:** Pick an odd number, let’s say n = 9.

![lbj1m](https://s3.amazonaws.com/discourseproduction/original/2X/8/81a52e0c9ec8f13aad3ab8f89fa87c23cdacec9a.png)

**Step-2:** Bend the above block of blocks in the middle.  
 ![part-2](https://s3.amazonaws.com/discourseproduction/original/2X/f/f5f8bc80f9d7865ccb17d3a7e7aefde2a7df8205.png)

**Step: 3** File the void space as shown below:  
 ![part-3](https://s3.amazonaws.com/discourseproduction/original/2X/e/e896c605ab36602f51fac4ba8ac607d3123053ab.png)

The grey area is what is p^{2} - q^{2}.

For our example where n = 9 which can be written as 9 = 5^{2} - 4^{2}, in the figure above the outer square is 5 \times 5 square and the inner one is 4 \times 4.

---

<div class="post-metadata">

**Author:** ![joestar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/joestar/32/3653_2.png) [@joestar](https://discuss.codechef.com/u/joestar)\
**Post date:** [April 13, 2020, 2:07pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/12 "2020-04-13T14:07:38Z")

</div>

[Here](https://ideone.com/Nrk612) is my approach to this problem. I handled even and odd numbers separately, and replaced odd numbers with 0, even with 1 and divisible by 4 with 2.  
For even numbers: for any subarray starting at _l_ and ending at _r_, if its product % 2 == 0, then _ans += n - r_ as all subarray starting at _l_ and ending at _k , k\>=r && k\<N_ will also be a part of the solution.  
For odd numbers: found a starting index _i_ and an ending index _j_ such that _arr[i:j]_ consists entirely of odd numbers, and updated _ans += k(k+1)/2 , k = j-i+1_  
However, this fails for all but one test case in subtask 2. Any pointers where I am going wrong?

---

<div class="post-metadata">

**Author:** ![hackslash\_123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hackslash_123/32/3653_2.png) [@hackslash\_123](https://discuss.codechef.com/u/hackslash_123)\
**Post date:** [April 13, 2020, 2:17pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/13 "2020-04-13T14:17:18Z")

</div>

You are calculating `total = n*(n+1)/2` without taking input `n`

---

<div class="post-metadata">

**Author:** ![hackslash\_123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hackslash_123/32/3653_2.png) [@hackslash\_123](https://discuss.codechef.com/u/hackslash_123)\
**Post date:** [April 13, 2020, 2:25pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/14 "2020-04-13T14:25:59Z")

</div>

This is an integer overflow issue. Know that `N` can be maximum `10^5`. Meaning answer can be upto `10^10`. Change all variables to `long long int`.

---

<div class="post-metadata">

**Author:** ![destroyer57](https://discuss.codechef.com/user_avatar/discuss.codechef.com/destroyer57/32/51714_2.png) [@destroyer57](https://discuss.codechef.com/u/destroyer57)\
**Post date:** [April 13, 2020, 2:26pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/15 "2020-04-13T14:26:35Z")

</div>

Got AC with same approach but it took 1 day to come along this way. Here my solution [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/31539777)

---

<div class="post-metadata">

**Author:** ![minhaj\_100](https://discuss.codechef.com/user_avatar/discuss.codechef.com/minhaj_100/32/13919_2.png) [@minhaj\_100](https://discuss.codechef.com/u/minhaj_100)\
**Post date:** [April 13, 2020, 2:27pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/16 "2020-04-13T14:27:25Z")

</div>

Hello,  
Can you tell me what is wrong with my solution…  
I tried to count all the invalid sub sequences and finally i subtract it from total sub array…

Got correct ans for every possible test cases in my mind…

But got wrong ans somehow…

It will be kind if anyone find a bug here or the test cases that i am getting wrong for…

Here is my solution :  
[http://codepad.org/ubaSqrvy](http://codepad.org/ubaSqrvy)

---

<div class="post-metadata">

**Author:** ![starters12](https://discuss.codechef.com/user_avatar/discuss.codechef.com/starters12/32/3653_2.png) [@starters12](https://discuss.codechef.com/u/starters12)\
**Post date:** [April 13, 2020, 2:28pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/17 "2020-04-13T14:28:54Z")

</div>

[https://www.codechef.com/viewsolution/31511874](https://www.codechef.com/viewsolution/31511874)  
can you please check i was getting wa in subtask 2…

---

<div class="post-metadata">

**Author:** ![ssrivastava990](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ssrivastava990/32/216836_2.png) [@ssrivastava990](https://discuss.codechef.com/u/ssrivastava990)\
**Post date:** [April 13, 2020, 2:29pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/18 "2020-04-13T14:29:53Z")

</div>

Wait for 2 hrs as cf contest is starting in 5 minutes 🙂

---

<div class="post-metadata">

**Author:** ![starters12](https://discuss.codechef.com/user_avatar/discuss.codechef.com/starters12/32/3653_2.png) [@starters12](https://discuss.codechef.com/u/starters12)\
**Post date:** [April 13, 2020, 2:32pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/19 "2020-04-13T14:32:53Z")

</div>

ok cool

---

<div class="post-metadata">

**Author:** ![sayan\_1999](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sayan_1999/32/208155_2.png) [@sayan\_1999](https://discuss.codechef.com/u/sayan_1999)\
**Post date:** [April 13, 2020, 2:44pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/20 "2020-04-13T14:44:16Z")

</div>

I am also getting WA in subtask 2. There is no integer overflow issue. My approach is  
1.Mark which numbers in the given array can be xpressed as p^2-q^2 in the success array.  
2.calculate total number of possible contiguous subsequences that equals n\*(n+1)/2.Store it in variable ans.  
3.from ans subtract all those contiguous subsequences that cannot be expressed in the given form.That happens only when the subsequence contains a single 2 as one of its factors and rest are odd.  
4.So I scan the array,stop at each element of the array that cannot be expressed as p^2-q^2 and check to see how many odd numbers are there to it’s left and to it’s right. The left odd number count is stored in k along with that number itself and the right odd count is stored in variable “count”. Then i subtract k and count and k\*count from ans to arrive at the final answer.

Is there anything wrong with my approach??I am really unable to see through it.I provide the link to my code  
[CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/31511240).

Note: I have got full marks on the problem due to some hard coding but I want to what is wrong with the given approach.  
Thanks to advance to the person who will kindly help me…

---

<div class="post-metadata">

**Author:** ![hackslash\_123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hackslash_123/32/3653_2.png) [@hackslash\_123](https://discuss.codechef.com/u/hackslash_123)\
**Post date:** [April 13, 2020, 2:47pm UTC](https://discuss.codechef.com/t/sqrdsub-editorial/61193/21 "2020-04-13T14:47:51Z")

</div>

Your approach is `O(N^2)`.

[Next page](https://discuss.codechef.com/t/sqrdsub-editorial/61193.md?page=2)