DSCPPAS266 - Editorial

editorial
,
1

Problem Statement:

You are given an array arr of positive integers. In each move, you can pick two different numbers from the array where their difference is at most one and remove the smaller one. If two numbers are the same, you can remove either. The goal is to determine if you can reduce the array to just one number using these moves.

Approach:

The problem can be approached by analyzing the differences between consecutive elements in the sorted array. The key observation is that for the array to be reducible to one number, every adjacent pair of elements must either be the same or differ by at most one. If any two consecutive elements in the sorted array differ by more than one, then it’s impossible to reduce the array to a single number.

Here is the step-by-step breakdown:

Step 1: Sort the Array

  • First, sort the array. Sorting helps us to check the difference between consecutive elements easily.

Step 2: Check Differences Between Consecutive Elements

  • Traverse the sorted array and check the difference between each consecutive pair of elements.
  • If the difference between any two consecutive elements is greater than one, it means that those two elements cannot be reduced to the same number, making it impossible to reduce the array to one number.

Step 3: Output the Result

  • If no consecutive elements have a difference greater than one, then it’s possible to reduce the array to one number, so print “YES”.
  • Otherwise, print “NO”.

Example:

Let’s consider an example to clarify the approach:

Example 1:

Input: arr = [2, 3, 3, 2, 4]
  • Step 1: Sort the array: [2, 2, 3, 3, 4]
  • Step 2: Check differences:
    • 2 - 2 = 0 (OK)
    • 3 - 2 = 1 (OK)
    • 3 - 3 = 0 (OK)
    • 4 - 3 = 1 (OK)
  • Step 3: All differences are ≤ 1, so the output is “YES”.

Example 2:

Input: arr = [1, 3, 5, 7]
  • Step 1: Sort the array: [1, 3, 5, 7]
  • Step 2: Check differences:
    • 3 - 1 = 2 (Not OK)
    • 5 - 3 = 2 (Not OK)
    • 7 - 5 = 2 (Not OK)
  • Step 3: There are differences greater than 1, so the output is “NO”.

Time Complexity:

  • Sorting: Sorting the array takes O(n log n).
  • Checking Differences: Checking differences takes O(n).

Overall, the time complexity is O(n log n).

Space Complexity:

  • The space complexity is O(1) beyond the input storage, as the algorithm only uses a fixed amount of extra space.