×

# May Challenge 2018 Minimum Deletion Help

 0 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 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"<

 3 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! answered 15 May '18, 00:50 991●1●15 accept rate: 38% 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)
 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. answered 15 May '18, 01:08 595●1●7 accept rate: 26%
 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? answered 15 May '18, 09:59 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) thanks. overall sequence gcd should equal to 1 (15 May '18, 14:17) Yes. Overall. (15 May '18, 14:32)
 0 Video solution here: https://youtu.be/6o3XSOKU0oc answered 16 May '18, 08:31 330●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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