search
HomeBackend DevelopmentPHP TutorialTake Gifts From the Richest Pile

Take Gifts From the Richest Pile

2558. Take Gifts From the Richest Pile

Difficulty: Easy

Topics: Array, Heap (Priority Queue), Simulation

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

  • Choose the pile with the maximum number of gifts.
  • If there is more than one pile with the maximum number of gifts, choose any.
  • Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

Example 1:

  • Input: gifts = [25,64,9,4,100], k = 4
  • Output: 29
  • Explanation: The gifts are taken in the following way:
    • In the first second, the last pile is chosen and 10 gifts are left behind.
    • Then the second pile is chosen and 8 gifts are left behind.
    • After that the first pile is chosen and 5 gifts are left behind.
    • Finally, the last pile is chosen again and 3 gifts are left behind.
    • The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

  • Input: gifts = [1,1,1,1], k = 4
  • Output: 4
  • Explanation: In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile.
    • That is, you can't take any pile with you.
    • So, the total gifts remaining are 4.

Constraints:

  • 1 3
  • 1 9
  • 1 3

Hint:

  1. How can you keep track of the largest gifts in the array
  2. What is an efficient way to find the square root of a number?
  3. Can you keep adding up the values of the gifts while ensuring they are in a certain order?
  4. Can we use a priority queue or heap here?

Solution:

We can utilize a max-heap (priority queue) since we need to repeatedly pick the pile with the maximum number of gifts. A max-heap will allow us to efficiently access the largest pile in constant time and update the heap after taking gifts from the pile.

Approach:

  1. Use a Max-Heap:

    • Since we need to repeatedly get the pile with the maximum number of gifts, a max-heap (priority queue) is ideal. In PHP, we can use SplPriorityQueue, which is a priority queue that by default works as a max-heap.
    • To simulate a max-heap, we will insert the number of gifts as a negative value, since SplPriorityQueue is a min-heap by default. By inserting negative values, the smallest negative value will represent the largest original number.
  2. Process Each Second:

    • In each second, pop the pile with the maximum number of gifts from the heap.
    • Take all the gifts except the floor of the square root of the number of gifts in that pile.
    • Push the modified pile back into the heap.
  3. Termination:

    • We stop after k seconds or once we've processed all the seconds.

Let's implement this solution in PHP: 2558. Take Gifts From the Richest Pile

<?php /**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

Explanation:

  1. Heap Initialization:

    • SplPriorityQueue is used to simulate a max-heap. The insert method allows us to push elements into the heap with a priority.
  2. Processing the Largest Pile:

    • For k iterations, the largest pile is extracted using extract.
    • The number of gifts left behind is calculated as the floor of the square root of the current largest pile using floor(sqrt(...)).
    • The reduced pile is re-inserted into the heap.
  3. Summing Remaining Gifts:

    • After the k operations, all elements in the heap are extracted and summed up to get the total number of remaining gifts.
  4. Edge Cases:

    • If gifts is empty, the result is 0.
    • If k is larger than the number of operations possible, the algorithm gracefully handles it.

Time Complexity:

  • Heap operations (insert and extract): Each heap operation (insertion and extraction) takes O(log n), where n is the number of piles.
  • Looping through k operations: We perform k operations, each involving heap extraction and insertion, both taking O(log n).

Thus, the total time complexity is O(k log n), where n is the number of piles and k is the number of seconds.

Example Walkthrough:

For the input:

<?php /**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>
  1. Initially, the priority queue has the piles: [25, 64, 9, 4, 100].
  2. After 1 second: Choose 100, leave 10 behind. The remaining gifts are: [25, 64, 9, 4, 10].
  3. After 2 seconds: Choose 64, leave 8 behind. The remaining gifts are: [25, 8, 9, 4, 10].
  4. After 3 seconds: Choose 25, leave 5 behind. The remaining gifts are: [5, 8, 9, 4, 10].
  5. After 4 seconds: Choose 10, leave 3 behind. The remaining gifts are: [5, 8, 9, 4, 3].

The sum of the remaining gifts is 5 8 9 4 3 = 29.

This approach efficiently solves the problem using a max-heap and performs well within the given constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

  • LinkedIn
  • GitHub

The above is the detailed content of Take Gifts From the Richest Pile. For more information, please follow other related articles on the PHP Chinese website!

Statement
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
PHP: An Introduction to the Server-Side Scripting LanguagePHP: An Introduction to the Server-Side Scripting LanguageApr 16, 2025 am 12:18 AM

PHP is a server-side scripting language used for dynamic web development and server-side applications. 1.PHP is an interpreted language that does not require compilation and is suitable for rapid development. 2. PHP code is embedded in HTML, making it easy to develop web pages. 3. PHP processes server-side logic, generates HTML output, and supports user interaction and data processing. 4. PHP can interact with the database, process form submission, and execute server-side tasks.

PHP and the Web: Exploring its Long-Term ImpactPHP and the Web: Exploring its Long-Term ImpactApr 16, 2025 am 12:17 AM

PHP has shaped the network over the past few decades and will continue to play an important role in web development. 1) PHP originated in 1994 and has become the first choice for developers due to its ease of use and seamless integration with MySQL. 2) Its core functions include generating dynamic content and integrating with the database, allowing the website to be updated in real time and displayed in personalized manner. 3) The wide application and ecosystem of PHP have driven its long-term impact, but it also faces version updates and security challenges. 4) Performance improvements in recent years, such as the release of PHP7, enable it to compete with modern languages. 5) In the future, PHP needs to deal with new challenges such as containerization and microservices, but its flexibility and active community make it adaptable.

Why Use PHP? Advantages and Benefits ExplainedWhy Use PHP? Advantages and Benefits ExplainedApr 16, 2025 am 12:16 AM

The core benefits of PHP include ease of learning, strong web development support, rich libraries and frameworks, high performance and scalability, cross-platform compatibility, and cost-effectiveness. 1) Easy to learn and use, suitable for beginners; 2) Good integration with web servers and supports multiple databases; 3) Have powerful frameworks such as Laravel; 4) High performance can be achieved through optimization; 5) Support multiple operating systems; 6) Open source to reduce development costs.

Debunking the Myths: Is PHP Really a Dead Language?Debunking the Myths: Is PHP Really a Dead Language?Apr 16, 2025 am 12:15 AM

PHP is not dead. 1) The PHP community actively solves performance and security issues, and PHP7.x improves performance. 2) PHP is suitable for modern web development and is widely used in large websites. 3) PHP is easy to learn and the server performs well, but the type system is not as strict as static languages. 4) PHP is still important in the fields of content management and e-commerce, and the ecosystem continues to evolve. 5) Optimize performance through OPcache and APC, and use OOP and design patterns to improve code quality.

The PHP vs. Python Debate: Which is Better?The PHP vs. Python Debate: Which is Better?Apr 16, 2025 am 12:03 AM

PHP and Python have their own advantages and disadvantages, and the choice depends on the project requirements. 1) PHP is suitable for web development, easy to learn, rich community resources, but the syntax is not modern enough, and performance and security need to be paid attention to. 2) Python is suitable for data science and machine learning, with concise syntax and easy to learn, but there are bottlenecks in execution speed and memory management.

PHP's Purpose: Building Dynamic WebsitesPHP's Purpose: Building Dynamic WebsitesApr 15, 2025 am 12:18 AM

PHP is used to build dynamic websites, and its core functions include: 1. Generate dynamic content and generate web pages in real time by connecting with the database; 2. Process user interaction and form submissions, verify inputs and respond to operations; 3. Manage sessions and user authentication to provide a personalized experience; 4. Optimize performance and follow best practices to improve website efficiency and security.

PHP: Handling Databases and Server-Side LogicPHP: Handling Databases and Server-Side LogicApr 15, 2025 am 12:15 AM

PHP uses MySQLi and PDO extensions to interact in database operations and server-side logic processing, and processes server-side logic through functions such as session management. 1) Use MySQLi or PDO to connect to the database and execute SQL queries. 2) Handle HTTP requests and user status through session management and other functions. 3) Use transactions to ensure the atomicity of database operations. 4) Prevent SQL injection, use exception handling and closing connections for debugging. 5) Optimize performance through indexing and cache, write highly readable code and perform error handling.

How do you prevent SQL Injection in PHP? (Prepared statements, PDO)How do you prevent SQL Injection in PHP? (Prepared statements, PDO)Apr 15, 2025 am 12:15 AM

Using preprocessing statements and PDO in PHP can effectively prevent SQL injection attacks. 1) Use PDO to connect to the database and set the error mode. 2) Create preprocessing statements through the prepare method and pass data using placeholders and execute methods. 3) Process query results and ensure the security and performance of the code.

See all articles

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)
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Chat Commands and How to Use Them
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use