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


May Challenge 2018 Minimum Deletion Help

Can anyone help in pointing out the mistake in my implementation of 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;
    while(t --)
        int n;
        int a[n];
        for(int i=1;i<=n;i++)
        int c = 0;
        int ans = a[1];
        for(int i=2;i<=n;i++)
            ans = gcd(ans,a[i]);
            if(ans != 1)
        if(c == n-1)
    return 0;

asked 14 May '18, 22:33

montycs's gravatar image

accept rate: 0%

The corrected solution:

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!


answered 15 May '18, 00:50

sarthakmanna's gravatar image

accept rate: 38%

edited 15 May '18, 00:54


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.


answered 15 May '18, 01:08

john_smith_3's gravatar image

accept rate: 26%

edited 15 May '18, 01:12


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?


answered 15 May '18, 09:59

sivayempalli's gravatar image

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:


answered 16 May '18, 08:31

code_report's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 14 May '18, 22:33

question was seen: 548 times

last updated: 16 May '18, 08:31