Table of Contents
method 1
algorithm
Example
Output
Method 2
Home Backend Development C++ Reduces an array to at most one element by the given operation

Reduces an array to at most one element by the given operation

Aug 29, 2023 pm 02:25 PM
Array operations reduce elements

Reduces an array to at most one element by the given operation

In this problem, we reduce the array size to 1 or 0 by performing the given operation every round.

We can sort the array in each round to get the maximum element in each iteration. In addition, we can also use the head data structure to improve the performance of the code.

Problem Statement - We are given a nums[] array. We need to reduce the array by doing the following.

  • Select the two largest elements in the array.

  • If two elements are the same, delete the two elements from the array.

  • If the two elements are not the same, delete the two elements from the array and insert abs(first − secondary) into the array.

Print the last element of the array. If the array is empty, print 0.

Example

enter

nums = {5, 9, 8, 3, 2, 5};
Copy after login

Output

0
Copy after login

illustrate

  • In the first round, we take 9 and 8 and add their difference to the array. Therefore, the array becomes [5, 3, 2, 5, 1].

  • In the second round, we take 5 and 5. Therefore, the array becomes [3, 2, 1].

  • Next round, we take 3 and 2. Therefore, the array becomes [1, 1]

  • In the last round, we take 1 and 1. Therefore, the array becomes empty and we print 0.

enter

nums = {5, 5, 5, 5, 5};
Copy after login

Output

5
Copy after login

Explanation- We delete a pair of 5 twice and there is one 5 remaining in the array.

enter

nums = {4, 8, 7, 6};
Copy after login

Output

1
Copy after login

Explanation - First, we select 8 and 7. Therefore, the array becomes [4, 1, 6]. After that, we select 4 and 6. Therefore, the array becomes [1, 2]. On the last operation, the array becomes [1].

method 1

In this method, we will iterate through the array until the size of the array becomes 1 or 0. In each iteration, we will sort the array and perform the given operation on the first 2 elements of the sorted array. Finally, we will print the output based on the array size.

algorithm

Step 1- Store the size of the array in the "len" variable.

Step 2- Start traversing the array using a while loop.

Step 3- Use the sort() method in a loop to sort the array in reverse.

Step 4- Get the first and second elements of the array. Also, calculate the difference between the first and second elements of the array.

Step 5− If the difference is 0, delete the first two elements of the array and reduce 'len' by 2. If the difference is not 0, delete the first 2 elements and decrement 'len' minus 1.

Step 6- Finally, if the size of the array is 0, return 0. Otherwise, the first element of the array is returned.

Example

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    int len = nums.size();
    int p = 0;
    while (len > 1) {
        // Sort array in reverse order
        sort(nums.begin(), nums.end(), greater<int>());
        // Take the first and second elements of the array
        int a = nums[0];
        int b = nums[1];
        // Take the difference between the first and second element
        int diff = a - b;
        if (diff == 0) {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            len -= 2;
        } else {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            nums.push_back(diff);
            len -= 1;
        }
    }
    // When the size of the array is 0
    if (nums.size() == 0)
        return 0;
    return nums[0];
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}
Copy after login

Output

The last remaining element after performing the given operations is 0
Copy after login
Copy after login

Time complexity - O(N*NlogN), where O(N) is used to iterate over the array and O(NlogN) is used to sort the array in each iteration.

Space complexity - O(N) to sort the array.

Method 2

In this approach, we will use a priority queue, which implements the heap data structure. It always stores elements in sorted order. So we can easily remove the first 2 largest elements.

algorithm

Step 1- Define "p_queue" named priority queue.

Step 2- Insert all array elements into the priority queue.

Step 3- Iterate until the size of the priority queue is greater than 1.

Step 4- Delete the first 2 elements of the priority queue one by one.

Step 5- Find the difference between two elements.

Step 6- If the difference is not 0, push it into the priority queue.

Step 7− Finally, if the queue size is 0, return 0.

Step 8 - Otherwise, return the element at the top of the queue.

Example

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    // Defining a priority queue
    priority_queue<int> p_queue;
    // Inserting array elements in priority queue
    for (int p = 0; p < nums.size(); ++p)
        p_queue.push(nums[p]);
    // Make iterations
    while (p_queue.size() > 1) {
        // Take the first element from queue
        int first = p_queue.top();
        p_queue.pop();
        // Get the second element from queue
        int second = p_queue.top();
        p_queue.pop();
        // Take the difference of first and second elements
        int diff = first - second;
        if (diff != 0)
            p_queue.push(diff);
    }
    // When queue is empty
    if (p_queue.size() == 0)
        return 0;
    // Return the last remaining element
    return p_queue.top();
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}
Copy after login

Output

The last remaining element after performing the given operations is 0
Copy after login
Copy after login

Time complexity - The time complexity of inserting and deleting elements in the priority queue is O(NlogN).

Space Complexity - O(N) to store elements in the priority queue.

Priority queue data structure is always useful when we need to arrange the array data in a specific order after inserting or deleting any element. It implements the heap data structure, thereby enabling insertion and deletion.

The above is the detailed content of Reduces an array to at most one element by the given operation. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

What are the types of values ​​returned by c language functions? What determines the return value? What are the types of values ​​returned by c language functions? What determines the return value? Mar 03, 2025 pm 05:52 PM

This article details C function return types, encompassing basic (int, float, char, etc.), derived (arrays, pointers, structs), and void types. The compiler determines the return type via the function declaration and the return statement, enforcing

Gulc: C library built from scratch Gulc: C library built from scratch Mar 03, 2025 pm 05:46 PM

Gulc is a high-performance C library prioritizing minimal overhead, aggressive inlining, and compiler optimization. Ideal for performance-critical applications like high-frequency trading and embedded systems, its design emphasizes simplicity, modul

What are the definitions and calling rules of c language functions and what are the What are the definitions and calling rules of c language functions and what are the Mar 03, 2025 pm 05:53 PM

This article explains C function declaration vs. definition, argument passing (by value and by pointer), return values, and common pitfalls like memory leaks and type mismatches. It emphasizes the importance of declarations for modularity and provi

C language function format letter case conversion steps C language function format letter case conversion steps Mar 03, 2025 pm 05:53 PM

This article details C functions for string case conversion. It explains using toupper() and tolower() from ctype.h, iterating through strings, and handling null terminators. Common pitfalls like forgetting ctype.h and modifying string literals are

Where is the return value of the c language function stored in memory? Where is the return value of the c language function stored in memory? Mar 03, 2025 pm 05:51 PM

This article examines C function return value storage. Small return values are typically stored in registers for speed; larger values may use pointers to memory (stack or heap), impacting lifetime and requiring manual memory management. Directly acc

distinct usage and phrase sharing distinct usage and phrase sharing Mar 03, 2025 pm 05:51 PM

This article analyzes the multifaceted uses of the adjective "distinct," exploring its grammatical functions, common phrases (e.g., "distinct from," "distinctly different"), and nuanced application in formal vs. informal

How do I use algorithms from the STL (sort, find, transform, etc.) efficiently? How do I use algorithms from the STL (sort, find, transform, etc.) efficiently? Mar 12, 2025 pm 04:52 PM

This article details efficient STL algorithm usage in C . It emphasizes data structure choice (vectors vs. lists), algorithm complexity analysis (e.g., std::sort vs. std::partial_sort), iterator usage, and parallel execution. Common pitfalls like

How does the C   Standard Template Library (STL) work? How does the C Standard Template Library (STL) work? Mar 12, 2025 pm 04:50 PM

This article explains the C Standard Template Library (STL), focusing on its core components: containers, iterators, algorithms, and functors. It details how these interact to enable generic programming, improving code efficiency and readability t

See all articles