SHARE
TWEET

Untitled

a guest Jan 13th, 2020 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5. )
  6.  
  7. func min(a int, b int) int {
  8.     if a < b { return a }
  9.     return b
  10. }
  11.  
  12. func f(a []int, bit int) int {
  13.     if (bit < 0) { return 0 }
  14.  
  15.     mask := 1 << uint(bit)
  16.  
  17.     var ones, zero []int
  18.     for _, v := range a {
  19.         if (mask & v) != 0 {
  20.             ones = append(ones, v)
  21.         } else {
  22.             zero = append(zero, v)
  23.         }
  24.     }
  25.  
  26.     if len(ones) == 0 { return f(zero, bit - 1) }
  27.     if len(zero) == 0 { return f(ones, bit - 1) }
  28.  
  29.     return mask + min(f(ones, bit - 1),
  30.                       f(zero, bit - 1));
  31. }
  32.  
  33. func main() {
  34.     var n int
  35.     fmt.Scanf("%d", &n)
  36.     a := make([]int, n)
  37.     for i := 0; i < n; i++ {
  38.         fmt.Scanf("%d", &a[i])
  39.     }
  40.     fmt.Printf("%d\n", f(a, 30))
  41. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top