I solved this question 1461D using a brute force method to find all valid sums in the array but one of my submission which seems correct to me doesnt seem to be working while another submission which is quite similar but just involves splitting and using it in a new vector gives a correct answer. Please help ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Pass your vector by reference and that's all.
Correct one:
I have resubmitted it here: 101179136
Thanks for that can you pls explain why it works that way ?
Every time the function is called, a separate copy of the vector is created. By passing it by reference, you can avoid that. That applies to strings too, or any other "large container"
You should always pass vector by reference to a function.
If a vector is passed by value, a new temporary vector will be copied. And copying a vector means dynamically allocating new memory for a new vector, copying all elements so it's much more slower.
If the vector is small, there is no problem, but if it is large, then the parameter-passing itself could consume a lot of resources.
Ok thanks for your help
But if without reference it means that we are copying the vector repeatedly then this submission which creates new vector for every stage also shouldnt work . Can you pls explain why this one works correctly ?
Because he's not passing the whole vector. He's dividing current vector into two halves, So in every recursion call vector size is reduced to half so space would be
ONlogN.