Add Lesson 10 - Flags solution (#1)

* Create Flags.go * Update README.md * Update Flags.go * Update README.md * Create NailingPlanks.go
theodesp · Sep 21, 2019 · 61beaf3 · 61beaf3
1 parent ee4d6f0
commit 61beaf3
Show file tree

Hide file tree

Showing 3 changed files with 161 additions and 1 deletion.
diff --git a/README.md b/README.md
@@ -57,7 +57,12 @@ comment.
     - [x] MinPerimeterRectangle
     - [ ] CountFactors
     - [ ] Peaks
-    - [ ] Flags
+    - [x] Flags
+
+- [ ] **Binary search**
+    - [x] NailingPlanks
+    - [ ] MinMaxDivision
+
 
 
 
diff --git a/binary-search/NailingPlanks.go b/binary-search/NailingPlanks.go
@@ -0,0 +1,112 @@
+package binary_search
+
+/*
+You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks. More precisely, A[K] is the start and B[K] the end of the K−th plank.
+
+Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.
+
+We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].
+
+The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].
+
+For example, given arrays A, B such that:
+
+    A[0] = 1    B[0] = 4
+    A[1] = 4    B[1] = 5
+    A[2] = 5    B[2] = 9
+    A[3] = 8    B[3] = 10
+four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].
+
+Given array C such that:
+
+    C[0] = 4
+    C[1] = 6
+    C[2] = 7
+    C[3] = 10
+    C[4] = 2
+if we use the following nails:
+
+0, then planks [1, 4] and [4, 5] will both be nailed.
+0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
+0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
+0, 1, 2, 3, then all the planks will be nailed.
+Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.
+
+Write a function:
+
+func Solution(A []int, B []int, C []int) int
+
+that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.
+
+If it is not possible to nail all the planks, the function should return −1.
+
+For example, given arrays A, B, C such that:
+
+    A[0] = 1    B[0] = 4
+    A[1] = 4    B[1] = 5
+    A[2] = 5    B[2] = 9
+    A[3] = 8    B[3] = 10
+
+    C[0] = 4
+    C[1] = 6
+    C[2] = 7
+    C[3] = 10
+    C[4] = 2
+the function should return 4, as explained above.
+
+Assume that:
+
+N and M are integers within the range [1..30,000];
+each element of arrays A, B, C is an integer within the range [1..2*M];
+A[K] ≤ B[K].
+Complexity:
+
+expected worst-case time complexity is O((N+M)*log(M));
+expected worst-case space complexity is O(M) (not counting the storage required for input arguments).
+*/
+
+func Solution(a []int, b []int, c []int) int {
+    n := len(a)
+    m := len(c)
+    minNails := 1
+    maxNails := m
+    var mid int
+    var missing bool
+
+    total := -1
+
+    maxCoord := m * 2 + 1
+    nailed := make([]int, maxCoord)
+
+    for ; minNails <= maxNails ; {
+        missing = false
+        mid = (maxNails + minNails) / 2
+
+        for i := 0 ; i < maxCoord ; i++ {
+            nailed[i] = 0
+        }
+
+        for i := 0 ; i < mid ; i++ {
+            nailed[c[i]]++
+        }   
+
+        for i := 1 ; i < maxCoord ; i++ {
+            nailed[i] = nailed[i] + nailed[i - 1]
+        }
+
+        for i := 0 ; i < n ; i++ {
+            if (nailed[a[i] - 1] == nailed[b[i]]) {
+                missing = true
+            }
+        }
+
+        if missing {
+            minNails = mid + 1
+        } else {
+            maxNails = mid - 1
+            total = mid
+        }
+    }
+
+    return total
+}
diff --git a/prime-composite/Flags.go b/prime-composite/Flags.go
@@ -0,0 +1,43 @@
+package prime_composite
+
+func Flags(a []int) int {
+    var numPicks int
+    var sumDist int
+    var distances = make([]int, len(a) / 2)
+    var lastPeakI int
+
+    // Count peaks and distances
+    for i := 1; i < len(a) - 1; i++ {
+        if a[i] > a[i-1] && a[i] > a[i+1] {
+            if lastPeakI != 0 {
+                distances[numPicks] = i - lastPeakI
+                sumDist += i - lastPeakI
+            }
+            numPicks++
+            lastPeakI = i
+        }
+    }
+
+    // Search maximum reasonable number of flags
+    for i := numPicks ; i > 0 ; i-- {
+        if i * (i - 1) <= sumDist {
+            // Test found number of flags
+            flags := 1
+            prevSum := 0
+            for j := 1 ; j < len(distances) ; j++ {
+                if prevSum + distances[j] >= i {
+                    flags++
+                    prevSum = 0
+                } else {
+                    prevSum += distances[j]
+                }
+            }
+
+            if flags >= i {
+                return i
+            }
+        } 
+    }
+
+    return 0
+}