Question

Can anyone help in pointing out the mistake in my implementation of https://www.codechef.com/MAY18B/problems/RD19 I am getting WA. Here is my implementation:

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    int dividend = a>=b?a:b;
    int divisor = a<=b?a:b;
    while(divisor != 0)
    {
        int remainder = dividend % divisor;
        dividend = divisor;
        divisor = remainder;
    }
    return dividend;
}

int main()
{
    int t;
    cin>>t;
    while(t --)
    {
        int n;
        cin>>n;
        int a[n];
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int c = 0;
        int ans = a[1];
        for(int i=2;i<=n;i++)
        {
            ans = gcd(ans,a[i]);
            if(ans != 1)
                c++;
        }
        if(c == n-1)
            cout<<"-1"<<endl;
        else
            cout<<c<<endl;
    }
    return 0;
}

Accepted Answer

The corrected solution: https://www.codechef.com/viewsolution/18574535

Firstly, observe the following:

gcd(a, b) <= min(a, b); ie. the gcd can only go down, as you calculate the common gcd of more and more numbers.
You need to find the minimum number of deletions to make gcd = 1. The minimum possible gcd of any number of positive numbers is 1. Hence, it is never beneficial to delete even a single element from the array of given numbers.

In other words, if you delete any element, chances are, the common gcd will go up. Therefore, it is never possible to bring the common gcd down to 1 by deletion, if the common gcd of all the elements is greater than 1.

Thus, the problem finally reduces to another problem, which asks you to print '0' if the common gcd is equal to 1, otherwise '-1'.

PS: Array index starts with 0. You cannot use 1-based indexing. You are lucky because C++ does not have OutOfBoundsException. Other programming languages like Python or Java will throw a RE with a similar code!

Answer 2

1

Two problems:

First, a[n] defines an array with elements a[0],a[1], ..., a[n-1]. So your loops should have the form

for (int i=0; i < n; i++)
{
}

Second, the minimum number of elements to be deleted is 0 or impossible. It is incorrect to output c as an answer.

link

answered 15 May '18, 01:08

6★john_smith_3
595●1●7
accept rate: 26%

edited 15 May '18, 01:12

Answer 3

0

@sarthakmanna

please explain with some input?

If input: 2 7 14 output: 1 //my approach if we delete 14 then gcd of this sequence is one Is my approach is right or wrong?

link

answered 15 May '18, 09:59

2★sivayempalli
1
accept rate: 0%

You don't need to delete anything... Even gcd(2, gcd(7, 14)) is 1. Hence, minimum number of deletion is 0; answer is 0.

(15 May '18, 10:28) sarthakmanna6★

thanks. overall sequence gcd should equal to 1

(15 May '18, 14:17) sivayempalli2★

Yes. Overall.

(15 May '18, 14:32) nileshjha193★

Answer 4

0	Video solution here: https://youtu.be/6o3XSOKU0oc link answered 16 May '18, 08:31 3★code_report 330●5 accept rate: 0%

May Challenge 2018 Minimum Deletion Help

Follow this question

Related questions