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

×

RD19 - Editorial

PROBLEM LINK:

Practice

Contest

Author: nileshjha19

Tester: Suchan Park

Editorialist: Suchan Park

DIFFICULTY:

Very Easy

PREREQUISITES:

How to compute GCD (Euclidean Algorithm)

PROBLEM:

You are given a sequence of integers of length $N$. You are allowed to delete up to $N-1$ elements in this sequence. Your goal is to make the GCD of the resulting sequence 1. Find whether it is possible, and if it's possible, find the minimum number of deletions.

QUICK EXPLANATION:

It makes no sense to remove any elements, since any such operation doesn't decrease the GCD and increase the number of deletions. Therefore the answer is $0$ if the GCD of the original array is 1, $-1$ otherwise.

EXPLANATION:

From the definition of GCD, we know that

$$\texttt{gcd}(a, b) \le \texttt{min}(a,b)$$

This means whenever we apply the GCD operation, the value does not increase. Therefore, the longer the sequence is, the smaller the GCD becomes.

Since we want to minimize the GCD and the number of deletions, we can see the best strategy is not deleting any of the elements!

If the GCD of the given sequence is 1, we are done. Otherwise, the GCD will not be 1 even if we delete some elements (since the GCD will not decrease), it is impossible to make the GCD 1.

Therefore the answer is $0$ if the GCD of the original array is 1, $-1$ otherwise.

We can compute the GCD of the whole array by:

$$\texttt{gcd}(A_1,\texttt{gcd}(A_2,\texttt{gcd}(A_3,\cdots,\texttt{gcd}(A_{n-1}, A_{n})\cdots))$$

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here

Tester's solution can be found here

Editorialist's solution can be found here.

This question is marked "community wiki".

asked 19 May, 06:45

tncks0121's gravatar image

2★tncks0121
139
accept rate: 0%

edited 22 May, 18:20

admin's gravatar image

0★admin ♦♦
19.6k349497539


Is there a comparable (more difficult) problem asking for the maximum number of elements that can removed and leave the gcd at $1$, or perhaps at whatever $\gcd(\{A_i\})$ is?

link

answered 14 Sep, 22:32

joffan's gravatar image

4★joffan
6657
accept rate: 11%

Not sure if the question is worded correctly. I originally had my program output the minimum number of deletions required to leave a sequence with GCD = 1.

That failed.

I switched it to output 0 if there existed a sequence, after deletions, with GCD = 1

It passed.

link

answered 13 Oct, 06:22

mrwishart's gravatar image

0★mrwishart
1
accept rate: 0%

Yep the problem is worded correctly. You output 0, that is no deletions are required to have GCD=1.

(13 Oct, 22:10) nileshjha193★
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:

×15,119
×1,554
×304
×106

question asked: 19 May, 06:45

question was seen: 1,549 times

last updated: 13 Oct, 22:11