Home > Mobile >  Reducing the process time of the sum of numbers code in Go
Reducing the process time of the sum of numbers code in Go

Time:02-15

I wrote this code, but the code test site rejected due to process time. To reduce time, I used Two pointers algorism, and Goroutine(I am not sure I used it correctly). But still that site rejected with the same reason. Is there any improvement solution to pass this? How can I reduce processing time. Please review my code. Thank you for your support!

Problem description

sequence of N numbers A[1], A[2], … , A[N] exists. The sum of numbers from i to j in this sequence A[i] A[i 1] … Write a program to find the number of cases where A[j-1] A[j] becomes M.

input

In the first line, N(1≤N≤10,000) and M(1≤M≤300,000,000) are given. The next line contains A[1], A[2], … , A[N] is given, separated by spaces. Each A[x] is a natural number not exceeding 30,000.

Print

the number of cases on the first line.

Example

  • input 1 :

    4 2

    1 1 1 1

  • output 1:

    3

  • input 2 :

    10 5

    1 2 3 4 2 5 3 1 1 2

  • output 2 :

    3

package main

import "fmt"

func main() {
    var n int //numbers
    var m int //target sum

    c := make(chan []int)
    d := make(chan int)

    fmt.Scanf("%d %d\n", &n, &m)
    arr := make([]int, n)
    go ReadN(arr, n, c)
    go checker(<-c, n, m, d)
    fmt.Print(<-d)
}

func ReadN(arr []int, n int, c chan<- []int) {
    for i := 0; i < n; i   {
        fmt.Scan(&arr[i])
    }
    c <- arr
}

func checker(arr []int, n, m int, d chan<- int) {
    var start int
    var end int
    var sum int
    var result int

    for start < n {
        if sum > m || end == n {
            sum -= arr[start]
            start  
        } else {
            sum  = arr[end]
            end  
        }
        if sum == m {
            result  
        }
    }
    d <- result
}

CodePudding user response:

Problem was from Scan and Scanf. It doesn't do any buffering, which makes it very slow if you get a lot of input. So I changed all Scan, Scanf to Fscan, Fscanf. Instead, I used bufio package. However, if you are not satisfied with the speed even with Fscanf(), you should seriously consider using a Scanner. See below code.

package main

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

func main() {
    var n int //numbers
    var m int //target sum
    var bufin *bufio.Reader = bufio.NewReader(os.Stdin)

    fmt.Fscanf(bufin, "%d %d\n", &n, &m)
    arr := make([]int, n)
    arr = ReadN(arr, n, bufin)
    result := checker(arr, n, m)
    fmt.Print(bufout, result)
}

func ReadN(arr []int, n int, bufin *bufio.Reader) []int {
    for i := 0; i < n; i   {
        fmt.Fscan(bufin, &arr[i])
    }
    return arr
}

func checker(arr []int, n, m int) int {
    var start int
    var end int
    var sum int
    var result int

    for start < n {
        if sum > m || end == n {
            sum -= arr[start]
            start  
        } else {
            sum  = arr[end]
            end  
        }
        if sum == m {
            result  
        }
    }
    return result
}

CodePudding user response:

You can solve this type of question using prefix-sum algorithm, which can do this in O(n) time and space. You can also refer to this article.

For practice on this type of questions, refer this

  • Related