Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

2028. Find the missing observational data

2028. Find out the missing observation data competition, medium

I. Title Description:

After a brief look at the problem, the first reaction is that this is a math problem. In fact, after a careful look, this is indeed a math problem, but we need to use the way of programming to achieve it. Let’s analyze it together

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

According to the information given in the question, we can know that there are these important points:

  • The given rolls array and the elements we need to add are in the range 1-6
  • Now we know the mean, we know the number of n+m, to calculate the missing data, or to find the whole observation
  • Find the array that corresponds to n, there could be many versions, and we only need to print one version

We can reason with an example:

Rolls = [1,5,6], mean = 3, n = 4

So we know, based on the simulation above, that the core point is to calculate the total of remainSum that can be given to n numbers, and if remainSum is less than n or if remainSum is greater than 6 times N, it doesn’t satisfy our question

When we get the required remainSum, we can allocate the values of the n numbers, and the logic of the allocation is very simple

So when we get the required remainSum, remainSum over n must be less than or equal to 6, and if it is equal to, there must be no remainder

So, our distributive principle is to take the remainder of remainSum % n and add it to each average

Three, coding

According to the above logic and analysis, we can translate into the following code, according to our mathematical way to deal with

The encoding is as follows:

func missingRolls(rolls []int, mean int, n int) []int {
    remainSum := mean * (len(rolls) + n )
    for _,num := range rolls {
        remainSum = remainSum - num
    }

    // If the remaining data is not between n and 6*n, the missing data is not found
    if remainSum < n || remainSum > 6 * n {
        return nil
    }

    // Start compiling data, where remainSum must be between n-6 *n, so remainSum/n must be shang less than 6, plus Yushu
    // We can construct a version of yushu shang+1, and (n-Yushu) Shang
    shang,yushu := remainSum/n , remainSum %n

    res := make([]int, n)
    for i:=0; i<n; i++{ res[i] = shangif i < yushu{
            res[i]++
        }
    }

    return res
}
Copy the code

The actual coding is indeed the translation of the above ideas, the translated code as above, mainly to consider the range of data n can carry, and how to allocate the value of N data

Iv. Summary:

It’s easy to understand that our loop here is n+m, so the time complexity is O(n+m), the space complexity is O(1).

Finding missing observational data

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~