fork download
copy 
  1. /*
  2.     Problem: Minimum Problems Solved Before Range Exceeds K
  3.     Company Tag: IBM OA
  4.  
  5.     Problem Statement:
  6.         We are given an integer array nums and an integer k.
  7.  
  8.         The student must solve problem 0 first.
  9.  
  10.         If the student solved problem i, next problem can be:
  11.             i + 1
  12.             i + 2
  13.  
  14.         The student stops as soon as:
  15.             max(solved values) - min(solved values) > k
  16.  
  17.         Return minimum number of problems solved before stopping.
  18.  
  19.         If impossible, return -1.
  20.  
  21.     Constraints:
  22.         Exact constraints were not mentioned.
  23.         This solution is O(n), so it works for large arrays.
  24.  
  25.     Brute Force:
  26.         Try all possible paths using jumps of 1 or 2.
  27.  
  28.     Why Brute Force Fails:
  29.         Number of paths grows exponentially.
  30.  
  31.     Optimized Idea:
  32.         Range exceeds k when two solved problems p and j satisfy:
  33.             abs(nums[p] - nums[j]) > k
  34.  
  35.         I process j from left to right.
  36.  
  37.         For previous indices, I maintain:
  38.             minimum value at even indices
  39.             maximum value at even indices
  40.             minimum value at odd indices
  41.             maximum value at odd indices
  42.  
  43.     Explanation Block:
  44.         The cost to include both p and j in a valid path depends only on:
  45.             - j
  46.             - parity of p
  47.  
  48.         That is why I store min/max values separately for even and odd indices.
  49.  
  50.         If current nums[j] differs from previous min/max by more than k,
  51.         then stopping is possible at j.
  52.  
  53.     Dry Run:
  54.         nums = [5, 6, 7, 20]
  55.         k = 3
  56.  
  57.         At index 3:
  58.             nums[3] = 20
  59.             previous minimum = 5
  60.             20 - 5 = 15 > 3
  61.  
  62.         One path:
  63.             0 -> 1 -> 3
  64.  
  65.         Solved values:
  66.             5, 6, 20
  67.  
  68.         Answer = 3
  69.  
  70.     Time Complexity:
  71.         O(n)
  72.  
  73.     Space Complexity:
  74.         O(1)
  75. */
  76.  
  77. #include <bits/stdc++.h>
  78. using namespace std;
  79.  
  80. int minimumProblemsBeforeRangeExceedsK(vector<long long>& nums, long long k) {
  81.     int n = nums.size();
  82.  
  83.     const int INF = 1e9;
  84.  
  85.     // mn[0], mx[0] store min/max values at even indices.
  86.     // mn[1], mx[1] store min/max values at odd indices.
  87.     vector<long long> mn(2, LLONG_MAX);
  88.     vector<long long> mx(2, LLONG_MIN);
  89.  
  90.     // Problem 0 is always solved first.
  91.     mn[0] = nums[0];
  92.     mx[0] = nums[0];
  93.  
  94.     int ans = INF;
  95.  
  96.     for (int j = 1; j < n; j++) {
  97.         long long x = nums[j];
  98.  
  99.         for (int parity = 0; parity <= 1; parity++) {
  100.             if (mn[parity] == LLONG_MAX) {
  101.                 continue;
  102.             }
  103.  
  104.             bool badPair = false;
  105.  
  106.             // Current value is much larger than previous minimum.
  107.             if (mn[parity] < x - k) {
  108.                 badPair = true;
  109.             }
  110.  
  111.             // Current value is much smaller than previous maximum.
  112.             if (mx[parity] > x + k) {
  113.                 badPair = true;
  114.             }
  115.  
  116.             if (badPair) {
  117.                 // Minimum solved count to reach j using jumps of 1 or 2.
  118.                 int solved = (j + 1) / 2 + 1;
  119.  
  120.                 // If j is even and previous index has odd parity,
  121.                 // one extra solved problem is needed.
  122.                 if (j % 2 == 0 && parity == 1) {
  123.                     solved++;
  124.                 }
  125.  
  126.                 ans = min(ans, solved);
  127.             }
  128.         }
  129.  
  130.         // Add current index for future checks.
  131.         int p = j % 2;
  132.  
  133.         mn[p] = min(mn[p], x);
  134.         mx[p] = max(mx[p], x);
  135.     }
  136.  
  137.     if (ans == INF) {
  138.         return -1;
  139.     }
  140.  
  141.     return ans;
  142. }
  143.  
  144. int main() {
  145.     vector<long long> nums = {5, 6, 7, 20};
  146.     long long k = 3;
  147.  
  148.     cout << minimumProblemsBeforeRangeExceedsK(nums, k) << endl;
  149.  
  150.     return 0;
  151. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/FGjTBq
language:
C++14 (gcc 8.3)
created:
1 day 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!