Mike's Beautiful Sequence

Easy

0/40

Contributed by

0 upvote

Asked in company

Problem statement

You are a data analyst working with a numerical sequence A of length n. A sequence is considered "beautiful" if the greatest common divisor (GCD) of all its elements is greater than 1.

To transform a sequence, you can perform a special operation:

- Choose an index i (where 1 <= i < n).
- Replace the two adjacent elements A[i] and A[i+1] with A[i] - A[i+1] and A[i] + A[i+1], respectively.

Your task is to find the minimum number of operations required to make the sequence A beautiful. If the sequence is already beautiful, no operations are needed.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer n, the length of the sequence.

The second line contains n space-separated integers, the elements of the sequence A.

Output Format:

The first line must be either "YES" or "NO". Since it is always possible to make the sequence beautiful, the answer will always be "YES".

If the answer is "YES", the second line must contain a single integer: the minimum number of operations required.

Note:

The most straightforward way to make the GCD of a sequence greater than 1 is to make all its elements even (so their GCD is at least 2).

Let's analyze the operation's effect on the parity (odd/even) of numbers:
- odd, odd -> (odd-odd), (odd+odd) -> even, even. This takes 1 operation to fix two adjacent odd numbers.

- odd, even -> (odd-even), (odd+even) -> odd, odd. This doesn't solve the problem directly, but it creates two adjacent odd numbers. We can then apply the first rule to this new pair. 
So, odd, even -> odd, odd -> even, even. This takes a total of 2 operations to fix a single odd number that is next to an even number.

The strategy is to iterate through the sequence and clear all odd numbers.

Sample Input 1:

3
1 3 2

Sample Output 1:

YES
1

Explanation for Sample 1:

The sequence is [1, 3, 2].

 - The first element, 1, is odd. The next element, 3, is also odd.

 - We can apply one operation on the pair (1, 3). They become (1-3, 1+3), which is (-2, 4).

 - The sequence becomes [-2, 4, 2]. All elements are now even. The GCD is at least 2.

 - This took a single operation.

Sample Input 2:

4
1 2 3 5

Sample Output 2:

YES
3

Explanation for Sample 2:

The sequence is [1, 2, 3, 5].

- The first element, 1, is odd. The next element, 2, is even. It will take 2 operations to make 1 even. After this, the sequence conceptually has only even numbers in the first two spots.

- We move to the next odd number, 3. The next element, 5, is also odd. We can pair them up. It takes 1 operation to make both 3 and 5 even.

- Total operations = 2 (for the 1) + 1 (for the pair 3, 5) = 3.

Expected Time Complexity:

The expected time complexity is O(N) for iterating through the array.

Constraints:

2 <= n <= 100,000
1 <= a[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Mike's Beautiful Sequence

Console