import Mathlib /-! # Number Complement The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation. For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer num, return its complement. ## Constraints - 1 <= num < 2^31 - Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/ ## Provided examples - `num = 5` → `2` - `num = 1` → `0` - `num = 8` → `7` ## Synthesized negative examples - invalid input: `num = 0` ([structural] a predicate that admits 1 <= num < 2^31. one below the lower bound; catches a predicate that allows zero) - invalid input: `num = 2147483648` ([structural] a predicate that admits 1 <= num < 2^31. equals the upper bound, which is exclusive; catches a predicate using <=) - invalid input: `num = 10000000000` ([structural] a predicate that admits 1 <= num < 2^31. order of magnitude past the ceiling; shape only, no new predicate) - `num = 5` → `3` is wrong ([structural] mask is one too high (2^bit_length instead of 2^bit_length-1). true complement is 2; using 8 as mask gives 3) - `num = 1` → `-2` is wrong ([structural] uses bitwise NOT on the integer rather than flipping only the bits of its binary representation.. treats leading ones from two's complement as part of the representation.) - `num = 8` → `6` is wrong ([structural] the least significant 0 is left unflipped due to an off-by-one mask. 8 becomes 0110 when the last 0 is left as 0) -/ namespace PNumberComplement abbrev Input := Nat abbrev Output := Int /-! ### Specification helpers -/ /-- `k` is the shortest positive bit length whose power-of-two bound exceeds `num`. -/ def IsBitLength (num k : Nat) : Prop := 0 < k ∧ 2 ^ (k - 1) ≤ num ∧ num < 2 ^ k /-! ### Validity predicate (V) -/ /-- Valid input: a positive natural number strictly below `2^31`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input < 2 ^ 31 /-! ### Ideal specification (P_spec) -/ /-- `result` is the complement of `input` beneath its shortest power-of-two mask. -/ def numberComplement_spec (input : Input) (result : Output) : Prop := ∃ k : Nat, input < 2 ^ k ∧ result + (input : Int) + 1 = (2 : Int) ^ k ∧ IsBitLength input k /-! ### Decidable specification (P_check) -/ /-- Finite checker for `numberComplement_spec` over the valid bit lengths below 32. -/ def numberComplement_check (input : Input) (result : Output) : Bool := (List.range 32).any fun k => decide (input < 2 ^ k ∧ result + (input : Int) + 1 = (2 : Int) ^ k ∧ 0 < k ∧ 2 ^ (k - 1) ≤ input) /-- The bit length of a number below `2 ^ 31` is below 32, which is what makes searching `List.range 32` lose nothing. -/ theorem bitLength_lt {input k : Nat} (hv : input < 2 ^ 31) (hpos : 0 < k) (hle : 2 ^ (k - 1) ≤ input) : k < 32 := by by_contra hcon have h31 : (2 : Nat) ^ 31 ≤ 2 ^ (k - 1) := Nat.pow_le_pow_right (by norm_num) (by omega) omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numberComplement_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numberComplement_check input result ↔ numberComplement_spec input result := by unfold numberComplement_check numberComplement_spec IsBitLength simp only [List.any_eq_true, decide_eq_true_eq, List.mem_range] simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h constructor · rintro ⟨k, _, hlt, heq, hpos, hle⟩ exact ⟨k, hlt, heq, hpos, hle, hlt⟩ · rintro ⟨k, hlt, heq, hpos, hle, _⟩ exact ⟨k, bitLength_lt h.2 hpos hle, hlt, heq, hpos, hle⟩ /-! ### Implementation helpers -/ /-- Smallest `k` with `n < 2^k`, by counting halvings of `n` down to zero. -/ def bitLengthOf (n : Nat) : Nat := if h : n = 0 then 0 else 1 + bitLengthOf (n / 2) termination_by n decreasing_by exact Nat.div_lt_self (Nat.pos_of_ne_zero h) (by decide) /-! ### Main algorithm (impl) -/ /-- Complement of `num` under its shortest power-of-two mask: `(2^k - 1) - num` with `k` the bit length. -/ def findComplement (num : Nat) : Int := ((2 ^ bitLengthOf num - 1 : Nat) - num : Int) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findComplement_correct (input : Input) (h : isValidInput input) : numberComplement_spec input (findComplement input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 5 #guard isValidInput 1 #guard isValidInput 8 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 2147483648) #guard !(isValidInput 10000000000) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numberComplement_check 5 2 #guard numberComplement_check 1 0 #guard numberComplement_check 8 7 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numberComplement_check 5 3) #guard !(numberComplement_check 1 (-2)) #guard !(numberComplement_check 8 6) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findComplement 5 == 2 #guard findComplement 1 == 0 #guard findComplement 8 == 7 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numberComplement_check 5 (findComplement 5) #guard numberComplement_check 1 (findComplement 1) #guard numberComplement_check 8 (findComplement 8) end PNumberComplement