fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. class SquareFinder {
  8. public:
  9.     int getKthSmallestSquare(const vector<int>& nums, int k) {
  10.         int n = nums.size();
  11.  
  12.         // 1. Binary Search to find the first non-negative element
  13.         // O(log N)
  14.         int right = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();
  15.         int left = right - 1;
  16.  
  17.         long long kthSquare = 0;
  18.         int count = 0;
  19.  
  20.         // 2. Expand outward k times
  21.         // O(K)
  22.         while (count < k) {
  23.             // Calculate squares for current pointers
  24.             // Use -1 or a large value to indicate out-of-bounds
  25.             long long leftSq = (left >= 0) ? (long long)nums[left] * nums[left] : -1;
  26.             long long rightSq = (right < n) ? (long long)nums[right] * nums[right] : -1;
  27.  
  28.             if (left < 0) {
  29.                 // Only positive numbers remain
  30.                 kthSquare = rightSq;
  31.                 right++;
  32.             } 
  33.             else if (right >= n) {
  34.                 // Only negative numbers remain
  35.                 kthSquare = leftSq;
  36.                 left--;
  37.             } 
  38.             else if (leftSq < rightSq) {
  39.                 // Negative number's square is smaller
  40.                 kthSquare = leftSq;
  41.                 left--;
  42.             } 
  43.             else {
  44.                 // Positive number's square is smaller
  45.                 kthSquare = rightSq;
  46.                 right++;
  47.             }
  48.  
  49.             count++;
  50.         }
  51.  
  52.         return (int)kthSquare;
  53.     }
  54. };
  55.  
  56. int main() {
  57.     SquareFinder sf;
  58.     // Sorted array
  59.     vector<int> nums = {-10, -5, -2, 0, 1, 3, 15};
  60.     int k = 4; 
  61.  
  62.     // Squares: 0, 1, 4, 9, 25, 100, 225
  63.     // 4th smallest should be 9
  64.     cout << "The " << k << "-th smallest square is: " << sf.getKthSmallestSquare(nums, k) << endl;
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The 4-th smallest square is: 9
https://ideone.com/vuGnH4
language:
C++ (gcc 8.3)
created:
14 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!