Header Ads Widget

Strong Elements | Codechef solution

Rajnish Tripathi 04:30

 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,…,�� - denoting the array �.

Output Format

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

Constraints

  • 1≤�≤5⋅104
  • 2≤�≤3⋅105
  • 1≤��≤109
  • Sum of � over all test cases do not exceed 3⋅105.

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
    {
        // your code goes here
        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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments