import Mathlib /-! # Continuous Subarray Sum Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise. A good subarray is a subarray where: its length is at least two, and the sum of the elements of the subarray is a multiple of k. Note that: A subarray is a contiguous part of the array. An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k. ## Constraints - 1 <= nums.length <= 10^5 - 0 <= nums[i] <= 10^9 - 0 <= sum(nums[i]) <= 2^31 - 1 - 1 <= k <= 2^31 - 1 ## Provided examples - `nums = [23, 2, 4, 6, 7], k = 6` → `true` - `nums = [23, 2, 6, 4, 7], k = 6` → `true` - `nums = [23, 2, 6, 4, 7], k = 13` → `false` ## Synthesized negative examples - invalid input: `nums = [], k = 1` ([structural] a predicate that admits 1 <= nums.length <= 10^5. empty array; predicate checking only the upper length limit accepts it) - invalid input: `nums = [-1, 1], k = 1` ([structural] a predicate that admits 0 <= nums[i] <= 10^9. negative element; predicate checking only the upper element bound accepts it) - invalid input: `nums = [1000000001], k = 1` ([structural] a predicate that admits 0 <= nums[i] <= 10^9. one past the element maximum) - `nums = [23, 2, 4, 6, 7], k = 6` → `false` is wrong ([structural] returns a fixed false instead of searching for a good subarray. trivial default; no condition forces a true result) - `nums = [23, 2, 6, 4, 7], k = 6` → `false` is wrong ([structural] omits the requirement to return true when a good subarray exists. false is the trivial boolean default) - `nums = [23, 2, 6, 4, 7], k = 13` → `true` is wrong ([structural] subarrays are not required to be contiguous. 6 and 7 sum to 13 but are not adjacent) -/ namespace PContinuousSubarraySum abbrev Input := (List Int) × (Nat) abbrev Output := Bool /-! ### Specification helpers -/ /-- The contiguous interval [startIdx, endIdx) of nums has length at least two and sums to n * k. -/ def IsGoodSubarray (nums : List Int) (k : Nat) (startIdx endIdx : Nat) (n : Int) : Prop := startIdx + 2 ≤ endIdx ∧ endIdx ≤ nums.length ∧ ((nums.drop startIdx).take (endIdx - startIdx)).sum = n * (k : Int) /-! ### Validity predicate (V) -/ /-- Valid input: 1 ≤ nums.length ≤ 10^5, every element in [0, 10^9], total sum ≤ 2^31 - 1, and 1 ≤ k ≤ 2^31 - 1. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 10^5 && input.1.all (fun x => 0 ≤ x && x ≤ 10^9) && input.1.sum ≤ 2^31 - 1 && 1 ≤ input.2 && input.2 ≤ 2^31 - 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when some contiguous subarray of length at least two sums to a multiple of k. -/ def hasGoodSubarray_spec (input : Input) (result : Output) : Prop := result = true ↔ ∃ (startIdx endIdx : Nat) (n : Int), IsGoodSubarray input.1 input.2 startIdx endIdx n /-! ### Decidable specification (P_check) -/ /-- Decide the subarray search by bounding both indices to `nums.length` and replacing the existential multiplier with decidable integer divisibility. -/ instance decidableGoodSubarrayExists (nums : List Int) (k : Nat) : Decidable (∃ startIdx endIdx n, IsGoodSubarray nums k startIdx endIdx n) := decidable_of_iff (∃ startIdx < nums.length + 1, ∃ endIdx < nums.length + 1, startIdx + 2 ≤ endIdx ∧ (k : Int) ∣ ((nums.drop startIdx).take (endIdx - startIdx)).sum) (by constructor · rintro ⟨startIdx, _, endIdx, hend, hge, hdvd⟩ rcases hdvd with ⟨n, hn⟩ refine ⟨startIdx, endIdx, n, hge, ?_, ?_⟩ · omega · rw [mul_comm] exact hn · rintro ⟨startIdx, endIdx, n, hge, hend, hsum⟩ refine ⟨startIdx, ?_, endIdx, ?_, hge, ⟨n, ?_⟩⟩ · omega · omega · rw [mul_comm] exact hsum) /-- Executable checker obtained mechanically from the specification. -/ def hasGoodSubarray_check (input : Input) (result : Output) : Bool := @decide (hasGoodSubarray_spec input result) (by unfold hasGoodSubarray_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem hasGoodSubarray_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : hasGoodSubarray_check input result ↔ hasGoodSubarray_spec input result := by simp [hasGoodSubarray_check] /-! ### Implementation helpers -/ /-- Adds a remainder-index pair to the map only when the remainder is not already present, preserving the earliest occurrence. -/ def insertEarliest (m : Std.TreeMap Int Nat) (r : Int) (idx : Nat) : Std.TreeMap Int Nat := match m.get? r with | some _ => m | none => m.insert r idx /-- Main loop over the remaining elements, carrying the running prefix sum, the current prefix index, and the earliest prefix index seen per remainder; returns true once a remainder repeats at distance at least two. -/ def scanPrefix (k : Nat) (xs : List Int) (sum : Int) (idx : Nat) (m : Std.TreeMap Int Nat) : Bool := match xs with | [] => false | x :: rest => let sum' := sum + x let idx' := idx + 1 let r := sum' % (k : Int) match m.get? r with | some j => if j + 2 ≤ idx' then true else scanPrefix k rest sum' idx' m | none => scanPrefix k rest sum' idx' (insertEarliest m r idx') /-! ### Main algorithm (impl) -/ /-- Scans prefix sums modulo k with a tree map from each remainder to its earliest prefix index, detecting a repeat at distance at least two. -/ def existsGoodSubarray (input : Input) : Output := scanPrefix input.2 input.1 0 0 ((Std.TreeMap.empty : Std.TreeMap Int Nat).insert 0 0) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem existsGoodSubarray_correct (input : Input) (h : isValidInput input) : hasGoodSubarray_spec input (existsGoodSubarray input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([23, 2, 4, 6, 7], 6) #guard isValidInput ([23, 2, 6, 4, 7], 6) #guard isValidInput ([23, 2, 6, 4, 7], 13) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 1)) #guard !(isValidInput ([(-1), 1], 1)) #guard !(isValidInput ([1000000001], 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard hasGoodSubarray_check ([23, 2, 4, 6, 7], 6) true #guard hasGoodSubarray_check ([23, 2, 6, 4, 7], 6) true #guard hasGoodSubarray_check ([23, 2, 6, 4, 7], 13) false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(hasGoodSubarray_check ([23, 2, 4, 6, 7], 6) false) #guard !(hasGoodSubarray_check ([23, 2, 6, 4, 7], 6) false) #guard !(hasGoodSubarray_check ([23, 2, 6, 4, 7], 13) true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard existsGoodSubarray ([23, 2, 4, 6, 7], 6) == true #guard existsGoodSubarray ([23, 2, 6, 4, 7], 6) == true #guard existsGoodSubarray ([23, 2, 6, 4, 7], 13) == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard hasGoodSubarray_check ([23, 2, 4, 6, 7], 6) (existsGoodSubarray ([23, 2, 4, 6, 7], 6)) #guard hasGoodSubarray_check ([23, 2, 6, 4, 7], 6) (existsGoodSubarray ([23, 2, 6, 4, 7], 6)) #guard hasGoodSubarray_check ([23, 2, 6, 4, 7], 13) (existsGoodSubarray ([23, 2, 6, 4, 7], 13)) end PContinuousSubarraySum