import Mathlib /-! # N Repeated Element In Size 2N Array You are given an integer array nums with the following properties: nums.length == 2 * n. nums contains n + 1 unique elements. Exactly one element of nums is repeated n times. Return the element that is repeated n times. ## Constraints - 2 <= n <= 5000 - nums.length == 2 * n - 0 <= nums[i] <= 10^4 - nums contains n + 1 unique elements and one of them is repeated exactly n times. ## Provided examples - `nums = [1, 2, 3, 3]` → `3` - `nums = [2, 1, 2, 5, 3, 2]` → `2` - `nums = [5, 1, 5, 2, 5, 3, 5, 4]` → `5` ## Synthesized negative examples - invalid input: `nums = [1, 2, 10001, 10001]` ([structural] a predicate that admits 0 <= nums[i] <= 10^4. one above the maximum; catches a predicate that checks repetition but not the upper bound) - invalid input: `nums = [1, 2, -1, -1]` ([structural] a predicate that admits 0 <= nums[i] <= 10^4. negative duplicate; catches a predicate that checks repetition but not the lower bound) - invalid input: `nums = [1, 2, 3, 4]` ([structural] a predicate that admits nums contains n + 1 unique elements and one of them is repeated exactly n times.. all unique; catches a predicate that checks values but not that any element repeats) - `nums = [1, 2, 3, 3]` → `1` is wrong ([structural] nothing requires the answer to be the repeated element. first element passes a membership-only spec) - `nums = [2, 1, 2, 5, 3, 2]` → `1` is wrong ([structural] answer required only to be one of the array's elements; no maximal-frequency requirement. 1 appears in nums but is not the repeated element) - `nums = [5, 1, 5, 2, 5, 3, 5, 4]` → `4` is wrong ([structural] does not require the output to appear n times; any element of nums is accepted. 4 is in nums but appears once, not n times) -/ namespace PNRepeatedElementInSize2nArray abbrev Input := List Int abbrev Output := Nat /-! ### Validity predicate (V) -/ /-- Valid input: length `2 * n` for some `2 ≤ n ≤ 5000`, with `n + 1` distinct values, exactly one value occurring exactly `n` times, and every entry in `[0, 10^4]`. -/ def isValidInput (input : Input) : Bool := let n := input.length / 2 decide (2 ≤ n) && decide (n ≤ 5000) && input.length == 2 * n && input.dedup.length == n + 1 && (input.dedup.filter (fun x => input.count x == n)).length == 1 && input.all (fun x => decide (0 ≤ x ∧ x ≤ 10 ^ 4)) /-! ### Ideal specification (P_spec) -/ /-- `result` occurs in `input`, and no element of `input` occurs more often than `result`. -/ def repeatedNTimes_spec (input : Input) (result : Output) : Prop := (result : Int) ∈ input ∧ ∀ x ∈ input, List.count x input ≤ List.count (result : Int) input /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def repeatedNTimes_check (input : Input) (result : Output) : Bool := @decide (repeatedNTimes_spec input result) (by unfold repeatedNTimes_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem repeatedNTimes_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : repeatedNTimes_check input result ↔ repeatedNTimes_spec input result := by simp [repeatedNTimes_check] /-! ### Implementation helpers -/ /-- First element of the list that occurs again within the next three positions, if any. -/ def firstDupWithin3 : List Int → Option Int | [] => none | x :: xs => if (xs.take 3).elem x then some x else firstDupWithin3 xs /-! ### Main algorithm (impl) -/ /-- Single left-to-right scan returning the first element repeated within the next three positions. -/ def findNRepeatedElement (nums : Input) : Output := match firstDupWithin3 nums with | some x => x.toNat | none => 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findNRepeatedElement_correct (input : Input) (h : isValidInput input) : repeatedNTimes_spec input (findNRepeatedElement input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3, 3] #guard isValidInput [2, 1, 2, 5, 3, 2] #guard isValidInput [5, 1, 5, 2, 5, 3, 5, 4] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [1, 2, 10001, 10001]) #guard !(isValidInput [1, 2, (-1), (-1)]) #guard !(isValidInput [1, 2, 3, 4]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard repeatedNTimes_check [1, 2, 3, 3] 3 #guard repeatedNTimes_check [2, 1, 2, 5, 3, 2] 2 #guard repeatedNTimes_check [5, 1, 5, 2, 5, 3, 5, 4] 5 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(repeatedNTimes_check [1, 2, 3, 3] 1) #guard !(repeatedNTimes_check [2, 1, 2, 5, 3, 2] 1) #guard !(repeatedNTimes_check [5, 1, 5, 2, 5, 3, 5, 4] 4) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findNRepeatedElement [1, 2, 3, 3] == 3 #guard findNRepeatedElement [2, 1, 2, 5, 3, 2] == 2 #guard findNRepeatedElement [5, 1, 5, 2, 5, 3, 5, 4] == 5 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard repeatedNTimes_check [1, 2, 3, 3] (findNRepeatedElement [1, 2, 3, 3]) #guard repeatedNTimes_check [2, 1, 2, 5, 3, 2] (findNRepeatedElement [2, 1, 2, 5, 3, 2]) #guard repeatedNTimes_check [5, 1, 5, 2, 5, 3, 5, 4] (findNRepeatedElement [5, 1, 5, 2, 5, 3, 5, 4]) end PNRepeatedElementInSize2nArray