14 days ago

Rohit • 40

Hyderabad

Question: Kth Smallest Stock Price

Problem Statement:

A stock trader trades in N selected stocks. The trader has calculated the relative stock price changes in the N stocks from the previous day's stock prices. The trader's lucky number is K, so the trader wants to invest in the particular stock that has the Kth smallest relative stock value.

Write an algorithm for the trader to find the Kth smallest stock price among the selected N stocks.

Input Format:

• The first line of the input consists of an integer - stock_size, representing the number of selected stocks (N).
• The second line consists of N space-separated integers representing the relative stock prices.
• (Based on the test case, a third line contains the integer K).

Sample Test Case 1:

Input:

7

1 2 3 4 5 7 9

4

Output:

4

just now

admin 1.9k

Hyderabad

Question: Kth Smallest Stock Price

Topics Involved / Prerequisites

• Sorting Algorithms
• Selection Algorithms
• Order Statistics

Overview

The objective is to identify the K-th smallest element in a collection of N stock prices. Since the trader is looking for the "lucky number" rank, we need to sort the data or use a selection method to pinpoint the value that would occupy the K-th position if the list were arranged in ascending order.

Approach

1. Read Inputs:
   • Read the total number of stocks (N).
   • Read the N relative prices into a vector or array.
   • Read the target rank (K).
2. Selection Strategy:
   • Option A (Sorting): Use std::sort() to arrange the entire array in O(N \log N) time. The answer is then located at prices[k-1].
   • Option B (Optimal Selection): Use std::nth_element(). This is a built-in C++ function that partially sorts the range so that the element at the K-th position is the same as it would be in a fully sorted array. This is more efficient as it runs in O(N) average time.
3. Output: Return the value at the K-th position (index K-1).

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int stock_size;
    // Step 1: Read the number of stocks
    if (!(cin >> stock_size)) return 0;

    vector<int> prices(stock_size);
    // Step 2: Read the relative stock prices
    for (int i = 0; i < stock_size; ++i) {
        cin >> prices[i];
    }

    int k;
    // Step 3: Read the lucky number K
    cin >> k;

    // Boundary check for K
    if (k < 1 || k > stock_size) {
        return 0;
    }

    // Step 4: Use nth_element to find the Kth smallest value in O(N) average time.
    // This rearranges the array so that the (k-1)-th element is in its 
    // sorted position.
    nth_element(prices.begin(), prices.begin() + (k - 1), prices.end());

    // Step 5: Output the result
    cout << prices[k - 1] << endl;

    return 0;
}

Time and Space Complexity

• Time Complexity: O(N \log N) if using standard sorting, or O(N) average if using std::nth_element. Given typical constraints for N, both are highly efficient.
• Space Complexity: O(N) to store the stock prices.