How to use moves logic in Golang? for example: I have an array = [1,2,3,4,5] so how can I create a function by using which all odd numbers come to the start of the array? and even number goes in the end in one move or at least in minimal moves?
3 Likes
Could this help you:
package main
import (
"fmt"
)
func main() {
list := []int{1, 2, 3, 4, 5, 6}
even := []int{}
odd := []int{}
sorted := []int{}
for i := range list {
if list[i]%2 == 0 {
even = append(even, list[i])
}
}
for i := range list {
if list[i]%2 != 0 {
odd = append(odd, list[i])
}
}
sorted = append(odd, even...)
fmt.Println(sorted)
}
2 Likes
I think the algorithm you’re looking for is “partition.” I wrote a naive implementation in the playground here that seems to work, but I wouldn’t put it into production without further testing:
https://play.golang.org/p/bBXucwR_Npg
To minimize moves, the partition is not stable. The pivot returned is the index that separates the values where the predicate evaluated to true vs. those where it was false, e.g.:
ints := []int{1, 2, 3, 4, 5}
pivot := partitionInts(ints, func(i int) bool { return i&1 == 1 })
odds := ints[:pivot]
evens := ints[pivot:]
A minimal move, efficient implementation:
package main
import "fmt"
func oddeven(a []int) {
for i, j := 0, len(a)-1; i < j; i++ {
if a[i]&1 == 0 {
for ; i < j; j-- {
if a[j]&1 != 0 {
a[i], a[j] = a[j], a[i]
break
}
}
}
}
}
func main() {
a := []int{1, 2, 3, 4, 5, 0, -1, -2, -3, -4, -5}
fmt.Println(a)
oddeven(a)
fmt.Println(a)
}
[1 2 3 4 5 0 -1 -2 -3 -4 -5]
[1 -5 3 -3 5 -1 0 -2 4 -4 2]
2 Likes
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.