I’m solving some easy problems to practice using Go, but I’m not sure if I’m reading the input correctly since I’m getting TLE even though my solution appears to have O(n) time complexity (10**5 constraints) here is the code and problem:
package main
import "fmt"
func main() {
// your code goes here
var testCases int
fmt.Scan(&testCases)
for ; testCases > 0; testCases-- {
var n int
fmt.Scan(&n)
slice := make([]int, n, n)
populateSlice(slice, n)
var firstSum, secondSum int
for _, val := range slice {
if val%2 == 0 {
if firstSum%2 == 1 {
firstSum += val
} else {
secondSum += val
}
} else {
if firstSum%2 == 0 {
firstSum += val
} else {
secondSum += val
}
}
}
if firstSum*secondSum%2 == 0 {
fmt.Println("NO")
} else {
fmt.Println("YES")
}
}
}
func populateSlice(slice []int, n int) {
for i := 0; i < n; i++ {
fmt.Scan(&slice[i])
}
}
I’m not sure how’s that suppose to help me understand where does that TLE comes from, you have the same time complexity, populate array O(n) and loop over that array O(n).
Single loop without unnecessary array also raises TLE.
package main
import "fmt"
func main() {
// your code goes here
var testCases int
fmt.Scan(&testCases)
for ; testCases > 0; testCases-- {
var n int
fmt.Scan(&n)
var firstSum, secondSum int
for ; n > 0; n-- {
var val int
fmt.Scan(&val)
if val%2 == 0 {
if firstSum%2 == 1 {
firstSum += val
} else {
secondSum += val
}
} else {
if firstSum%2 == 0 {
firstSum += val
} else {
secondSum += val
}
}
}
if firstSum*secondSum%2 == 0 {
fmt.Println("NO")
} else {
fmt.Println("YES")
}
}
}
I’ve rewrote this with bufio’s scanner as fmt.Scan() reads stdin as space/new-line separated and according to chatGPT each read comes from the hard drive (it’s not preloaded into RAM, not sure about this) with redirect go run main.go < input.txt.
However by looking at @dpcoder_007 solution c++ reads the same, so it shouldn’t be the problem.
Now I’m getting the wrong answer for the input with 1000 elements, I even tried to use @dpcoder_007 logic, but I get the same result, here’s the code:
package main
import "fmt"
import "bufio"
import "os"
import "strconv"
import "strings"
func main() {
// your code goes here
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
line := scanner.Text()
testCases, _ := strconv.Atoi(line)
for ; testCases > 0; testCases-- {
scanner.Scan()
scanner.Text()
scanner.Scan()
line = scanner.Text()
slice := strings.Split(line, " ")
var sum, sum2 int
for _, strVal := range slice {
val, _ := strconv.Atoi(strVal)
sum += val
}
var possible bool
for _, strVal := range slice {
val, _ := strconv.Atoi(strVal)
sum -= val
sum2 += val
if sum%2 == 1 && sum2%2 == 1 {
possible = true
}
}
if possible {
fmt.Println("YES")
} else {
fmt.Println("NO")
}
}
}
Same thing happens when I combine fmt.Scan() as I did in the first post with @dpcoder_007 logic on my local machine with that 1000 input (or I have made some mistake).
Thanks for the heads-up, I’m not sure how to deal with integer overflow in this case: I’ve tried using modulo 1_000_000_007 but it won’t work, I have even tried in Python to be sure I’m not making any mistakes:
MOD = 1_000_000_007
testCases = int(input())
while testCases > 0:
lenght = int(input())
slice = [int(x) for x in input().split(" ")]
sum1 = 0
for val in slice:
sum1 = (sum1 + val) % MOD
sum2 = 0
possible = False
for val in slice:
sum1 = (sum1 - val + MOD) % MOD
sum2 = (sum1 + val) % MOD
if sum1%2 and sum2%2:
possible = True
if possible:
print("YES")
else:
print("NO")
testCases -= 1
this doesn’t work, replacing all the % MOD operation with simple += and -= results in a correct answer though.
I have figured it out, it appears that there is a testcase in which sum is equal to 1 000 000 007 and 1 000 000 007 % 1 000 000 007 will result in 0 (in this case the parity is altered).
Btw. my logic also passes.