fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. using namespace std;
  5.  
  6. int longestSubarrayNotDivisibleByX(const vector<int>& b, int x) {
  7.     int n = b.size();
  8.     unordered_map<int, int> first_occurrence;  // mod value -> first index
  9.     int prefix_sum = 0;
  10.     int max_len = -1;  // no valid subarray yet
  11.  
  12.     for (int i = 0; i < n; ++i) {
  13.         prefix_sum += b[i];
  14.  
  15.         // ⚠️ Step 1: Compute safe mod
  16.         int mod = ((prefix_sum % x) + x) % x;
  17.  
  18.         // ✅ Case 1: sum from 0 to i is not divisible by x
  19.         if (mod != 0) {
  20.             max_len = max(max_len, i + 1);
  21.         }
  22.  
  23.         // ❌ Case 2: mod == 0 -> sum divisible by x
  24.         // Try to skip some prefix to get non-divisible sum
  25.         if (first_occurrence.count(mod)) {
  26.             int j = first_occurrence[mod];
  27.             max_len = max(max_len, i - j);  // remove prefix up to j
  28.         } else {
  29.             first_occurrence[mod] = i;  // store only first occurrence
  30.         }
  31.     }
  32.  
  33.     return max_len;
  34. }
  35. int main() {
  36.     vector<int> b = {3, 1, 2, 2, 4}; 
  37.     int x = 3;
  38.  
  39.     int result = longestSubarrayNotDivisibleByX(b, x);
  40.     cout << "Longest subarray length (sum not divisible by " << x << "): " << result << endl;
  41.  
  42.     return 0;
  43. }
  44.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Longest subarray length (sum not divisible by 3): 4
https://ideone.com/4XvsrR
language:
C++ (gcc 8.3)
created:
160 days 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!