You are not logged in. Please login at www.codechef.com to post your questions!

×

May Challenge 2018 Minimum Deletion Help

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

asked 14 May '18, 22:33

montycs's gravatar image

0★montycs
1057
accept rate: 0%


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!

link

answered 15 May '18, 00:50

sarthakmanna's gravatar image

6★sarthakmanna
991115
accept rate: 38%

edited 15 May '18, 00:54

1

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

(15 May '18, 22:21) montycs0★

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

(15 May '18, 22:55) nileshjha193★

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

john_smith_3's gravatar image

6★john_smith_3
59517
accept rate: 26%

edited 15 May '18, 01:12

@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

sivayempalli's gravatar image

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★

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

link

answered 16 May '18, 08:31

code_report's gravatar image

3★code_report
3305
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,719

question asked: 14 May '18, 22:33

question was seen: 548 times

last updated: 16 May '18, 08:31