# Strong Elements | Codechef solution

Problem

Chef has an array $�$ of length $�$.

An index $�$ is called strong if we can change the gcd of the whole array just by changing the value of ${�}_{�}$.

Determine the number of strong indices in the array.

### Input Format

• First line will contain $�$, number of test cases. Then the test cases follow.
• First line of each test case contains an integer $�$ denoting the size of the array $�$.
• Second line contains $�$ space separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$ - denoting the array $�$.

### Output Format

For each test case, output the number of strong indices in the array.

### Constraints

• $1\le �\le 5\cdot 1{0}^{4}$
• $2\le �\le 3\cdot 1{0}^{5}$
• $1\le {�}_{�}\le 1{0}^{9}$
• Sum of $�$ over all test cases do not exceed $3\cdot 1{0}^{5}$.

### Sample 1:

Input
Output
3
3
5 10 20
4
3 5 7 11
4
2 2 2 2

3
0
4


### Explanation:

Test Case $1$: All the indices are strong.

• For index $1$ you can change the element to $10$ which changes the gcd of the array to $10$.
• For index $2$ you can change the element to $12$ which changes the gcd of the array to $1$.
• For index $3$ you can change the element to $12$ which changes the gcd of the array to $1$.

Test Case $2$: No index is strong. If you change any single element, gcd still remains the same.

Test Case $3$: All the indices are strong. You can change any element to $3$. This changes the gcd of the array to $1$

Code(C++):-

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t--)
{
//code here
int n;
cin>>n;
int gcd= 0;
vector<int> G(n);
for(int i=0;i<n;i++)
{
// int a;
cin>>G[i];

gcd = __gcd(gcd,G[i]);

}
if(gcd!=1) cout<<n<<endl;
else{
vector<int> prefix_gcd(n);
vector<int> suffix_gcd(n);
prefix_gcd[0] = G[0];
suffix_gcd[n-1] = G[n-1];
for(int i = 1; i < n ; i ++ )
{
prefix_gcd[i] = __gcd(G[i],prefix_gcd[i-1]);
}

for(int i = n-2; i >=0; i -- )
{
suffix_gcd[i] = __gcd(G[i],suffix_gcd[i+1]);
}

int count = 0;
for(int i = 0 ; i < n ; i ++ )
{
if(i==0)
{
if(suffix_gcd[1] > 1)
count++;
}
else if(i == n-1)
{
if( prefix_gcd[n-2] > 1)
count++;
}

else if ( __gcd( prefix_gcd[i-1] , suffix_gcd[i+1] ) > 1)
count++;
}
cout<<count<<endl;
}
}
return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}

int left[]=new int[n];
int right[]=new int[n];

left[0]=a[0];
right[n-1]=a[n-1];

for(int i=1;i<n;i++)
{
left[i]=gcd(left[i-1],a[i]);
}
for(int i=n-2;i>=0;i--)
{
right[i]=gcd(right[i+1],a[i]);
}
int count=0;
for(int i=0;i<n;i++)
{
if(i==0 && right[i+1]>1)
{
count++;
}
else if((i==n-1) && (left[i-1]>1))
{
count++;
}
else if(i!=0 && i!=n-1 && gcd(left[i-1],right[i+1])>1)
{
count++;
}
}
System.out.println(count);
}

}

public static int gcd(int a,int b){
if(a==0)
return b;

return gcd(b%a,a);
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-