How to find the 3 products with the minimum cost from a given array in C++

1 Answer

0 votes
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <iomanip>

/*
    This program demonstrates how to find the 3 products with the lowest cost
    from a list of product–price pairs.

    We use:
      - std::vector for storage
      - std::partial_sort for efficient selection of the smallest 3 items
      - clear helper functions
      - detailed comments explaining each step
*/

// A simple struct to hold product data
struct Product {
    std::string name;
    int price; // price in dollars
};

// Generate random products with prices between 1 and 20
std::vector<Product> generateProducts(int total_products) {
    std::vector<Product> products;
    products.reserve(total_products);

    // Random engine setup
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(1, 20);

    // Create p1, p2, ..., total_products
    for (int i = 1; i <= total_products; i++) {
        products.push_back(Product{"p" + std::to_string(i), dist(gen)});
    }

    return products;
}

// Print all products
void printProducts(const std::vector<Product>& products) {
    std::cout << "All products:\n";
    for (const auto& p : products) {
        std::cout << "  " << std::setw(3) << p.name << "  $" << p.price << "\n";
    }
    std::cout << "\n";
}

// Find the 3 cheapest products using partial_sort
std::vector<Product> findThreeCheapest(std::vector<Product> products) {
    /*
        partial_sort rearranges the first k elements into sorted order,
        and ensures they are the k smallest elements overall.

        This is more efficient than sorting the entire array when we only
        need a small subset.
    */

    const std::size_t k = 3;

    std::partial_sort(
        products.begin(),
        products.begin() + k,
        products.end(),
        [](const Product& a, const Product& b) {
            return a.price < b.price; // sort by price ascending
        }
    );

    // Return only the first 3 items
    return {products.begin(), products.begin() + k};
}

int main() {
    // Generate random products
    auto products = generateProducts(10);

    // Display all products
    printProducts(products);

    // Find the 3 cheapest
    auto cheapest = findThreeCheapest(products);

    // Display the result
    std::cout << "Three cheapest products:\n";
    for (const auto& p : cheapest) {
        std::cout << "  " << std::setw(3) << p.name << "  $" << p.price << "\n";
    }
}


/*
run:

All products:
   p1  $11
   p2  $2
   p3  $7
   p4  $1
   p5  $18
   p6  $16
   p7  $20
   p8  $17
   p9  $15
  p10  $9

Three cheapest products:
   p4  $1
   p2  $2
   p3  $7

*/

 



answered Aug 29 by avibootz
...