May Challenge 2018 Minimum Deletion Help

help
1

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;
}
2

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

Firstly, observe the following:

  1. gcd(a, b) <= min(a, b); ie. the gcd can only go down, as you calculate the common gcd of more and more numbers.
  2. 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!

3 Likes
3

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.

1 Like
4

@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?

5

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.

6

thanks.
overall sequence gcd should equal to 1

7

Yes. Overall.

8

Thanks for your answer. Since the problem explicitly said “find the minimum number of elements which have to be deleted”, I fell for it…

1 Like
9

No problem buddy. I hope you learnt something. :slight_smile:

10

Video solution here: https://youtu.be/6o3XSOKU0oc