import Mathlib /-! # Find All Duplicates In An Array Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice. You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output ## Constraints - n == nums.length - 1 <= n <= 10^5 - 1 <= nums[i] <= n - Each element in nums appears once or twice. ## Provided examples - `nums = [4, 3, 2, 7, 8, 2, 3, 1]` → `[2, 3]` - `nums = [1, 1, 2]` → `[1]` - `nums = [1]` → `[]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= n <= 10^5. empty array where at least one element is required) - invalid input: `nums = [0]` ([structural] a predicate that admits 1 <= nums[i] <= n. zero is below the minimum allowed value) - invalid input: `nums = [1, 1, 1]` ([structural] a predicate that admits Each element in nums appears once or twice.. one appears three times; a range-only predicate accepts it) - `nums = [4, 3, 2, 7, 8, 2, 3, 1]` → `[]` is wrong ([structural] completeness omitted. empty list is sound but incomplete) - `nums = [1, 1, 2]` → `[1, 2]` is wrong ([structural] output need not contain only duplicates. contains 1 but adds non-duplicate 2) - `nums = [1]` → `[1]` is wrong ([structural] frequency threshold off by one: reported integers that appear once instead of twice. 1 appears once; a one-off threshold includes it) -/ namespace PFindAllDuplicatesInAnArray abbrev Input := List Int abbrev Output := List Int /-! ### Specification helpers -/ /-- `x` occurs exactly twice in `nums`. -/ def OccursTwice (nums : List Int) (x : Int) : Prop := nums.count x = 2 /-! ### Validity predicate (V) -/ /-- Valid input: 1 ≤ length ≤ 10^5, every element in [1, length], each appearing at most twice. -/ def isValidInput (nums : Input) : Bool := 1 ≤ nums.length && nums.length ≤ 10^5 && nums.all (fun x => 1 ≤ x && x ≤ nums.length) && nums.all (fun x => nums.count x ≤ 2) /-! ### Ideal specification (P_spec) -/ /-- `result` lists, without repetition, exactly the values that occur twice in `input`. -/ def findDuplicates_spec (input : Input) (result : Output) : Prop := result.Nodup ∧ (∀ x ∈ result, OccursTwice input x) ∧ ∀ x, OccursTwice input x → x ∈ result /-! ### Decidable specification (P_check) -/ /-- Decides `OccursTwice nums x` by unfolding it to the decidable `Nat` equality `nums.count x = 2`. -/ instance decOccursTwice (nums : List Int) (x : Int) : Decidable (OccursTwice nums x) := inferInstanceAs (Decidable (nums.count x = 2)) /-- Decides the specification's completeness clause `∀ x, OccursTwice input x → x ∈ result` by bounding the quantifier to `input`: any value with count 2 is a member of `input`, so the bounded form over the list (which Lean decides via `List.decidableBAll`) is equivalent. -/ instance decAllOccursTwiceMem (input result : List Int) : Decidable (∀ x, OccursTwice input x → x ∈ result) := decidable_of_iff (∀ x ∈ input, OccursTwice input x → x ∈ result) ⟨fun h x hx => h x (List.count_pos_iff.mp (by have h2 : List.count x input = 2 := hx rw [h2] decide)) hx, fun h x _ hx => h x hx⟩ /-- Executable checker obtained mechanically from the specification. -/ def findDuplicates_check (input : Input) (result : Output) : Bool := @decide (findDuplicates_spec input result) (by unfold findDuplicates_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem findDuplicates_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : findDuplicates_check input result ↔ findDuplicates_spec input result := by simp [findDuplicates_check] /-! ### Implementation helpers -/ /-- Sign-marking scan over indices below `n`: cell `x - 1` is negated when value `x` is first seen, and a value whose cell is already negative is a duplicate, collected in reverse encounter order. -/ def markAndCollect (n : Nat) (arr : Array Int) (i : Nat) (acc : List Int) : List Int := if i < n then let x := (arr.getD i 0).natAbs let k := x - 1 let cell := arr.getD k 0 if cell < 0 then markAndCollect n arr (i + 1) ((x : Int) :: acc) else let arr' := if h : k < arr.size then arr.set k (-cell) h else arr markAndCollect n arr' (i + 1) acc else acc termination_by n - i /-! ### Main algorithm (impl) -/ /-- In-place sign-marking scan: values index cells of a one-pass array build, and a negated cell flags an already-seen value, in O(n) total. -/ def findDuplicatesArray (input : Input) : Output := let arr := input.toArray (markAndCollect arr.size arr 0 []).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findDuplicatesArray_correct (input : Input) (h : isValidInput input) : findDuplicates_spec input (findDuplicatesArray input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [4, 3, 2, 7, 8, 2, 3, 1] #guard isValidInput [1, 1, 2] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [0]) #guard !(isValidInput [1, 1, 1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard findDuplicates_check [4, 3, 2, 7, 8, 2, 3, 1] [2, 3] #guard findDuplicates_check [1, 1, 2] [1] #guard findDuplicates_check [1] [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(findDuplicates_check [4, 3, 2, 7, 8, 2, 3, 1] []) #guard !(findDuplicates_check [1, 1, 2] [1, 2]) #guard !(findDuplicates_check [1] [1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findDuplicatesArray [4, 3, 2, 7, 8, 2, 3, 1] == [2, 3] #guard findDuplicatesArray [1, 1, 2] == [1] #guard findDuplicatesArray [1] == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard findDuplicates_check [4, 3, 2, 7, 8, 2, 3, 1] (findDuplicatesArray [4, 3, 2, 7, 8, 2, 3, 1]) #guard findDuplicates_check [1, 1, 2] (findDuplicatesArray [1, 1, 2]) #guard findDuplicates_check [1] (findDuplicatesArray [1]) end PFindAllDuplicatesInAnArray