How Can I Optimize My SPOJ Solution to Avoid Timeouts?

Faster Input Scanning for SPOJ

Your SPOJ solution times out because the default input and output functions (fmt.Scan and fmt.Println) are relatively slow. To achieve faster input reading, utilize bufio.Scanner to read lines from the standard input.

Optimizing for Integer Conversion

Instead of using bufio.Scanner.Text() to obtain the text representation and then converting it to an integer using strconv.Atoi(), employ a dedicated conversion function to extract the number directly from the raw bytes returned by bufio.Scanner.Bytes(). This method avoids unnecessary string conversions and memory allocation, significantly improving performance.

func toInt(buf []byte) (n int) {
    for _, v := range buf {
        n = n*10 + int(v-'0')
    }
    return
}

Complete Optimized Solution

The following optimized solution reads input much faster and meets the SPOJ time limit requirements:

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    var n, k, c int
    scanner := bufio.NewScanner(os.Stdin)

    scanner.Scan()
    fmt.Sscanf(scanner.Text(), "%d %d", &n, &k)

    for ; n > 0; n-- {
        scanner.Scan()
        if toInt(scanner.Bytes())%k == 0 {
            c++
        }
    }

    fmt.Println(c)
}

func toInt(buf []byte) (n int) {
    for _, v := range buf {
        n = n*10 + int(v-'0')
    }
    return
}

Additional Notes

• The solution assumes valid input with at least n lines after the header.
• For closed input after n 1 lines, a simplified loop can be used:

for scanner.Scan() {
    if toInt(scanner.Bytes())%k == 0 {
        c++
    }
}

The above is the detailed content of How Can I Optimize My SPOJ Solution to Avoid Timeouts?. For more information, please follow other related articles on the PHP Chinese website!