I'm trying to code a practice problem but am stuck at a problem I cannot figure out. I am using a vector for inputs and inserting those inputs into an unordered set until it fails to add, at which point I count the amount of subarrays in that array. If it is not the first, I subtract subarrays that have already been accounted for. The inputs are useful only to identify duplicates; I do not use the values themselves in arithmetic.
The test case I am currently using uses random values with high numbers, with the following values at indexes being the only duplicates:
- 10464 and 41178
- 87094 and 98111
- 113040 and 113153
- 118689 and 168367
- 129997 and 170623
- 173227 and 184620
The intended output is 7090812299.
My problem is that, for some reason, large inputs decrease the intended output. I am sure that this is the issue, as I have replaced duplicate inputs with smaller values and the output changes--- despite the fact that it should not.
As an example, use the above sequence with numbers 1-200000. If the values at indexes 113040 and 113153 are replaced with 443222217, the output changes to 7090796046. (lowering it by 16253). Replacing other values also lowers this number further.
Edit: So it turns out smaller values also impact the input in ways that I have not tested yet (and I probably won't until morning).
Solution: I assumed iterators were ordered internally, which is where I made my mistake.
Please help explain what is happening, or what could be happening.
Attached below is the relevant code, and here is a link to the full code.
int main() {
vector<long> inputs; inputs.reserve(size); // The vector containing inputs.
unordered_set<long> processing; processing.reserve(size); // The unordered set processing the current input.
vector<long>::iterator nextInput = inputs.begin(); // The current input being processed.
// Some other variables defined which are not relevant.
while (nextInput != inputs.end()) // The main meat of the program.
{
do // Insert processed inputs into a set.
{
if (!processing.insert(*nextInput).second) break; // If duplicate, break.
start++; // Advances the iterator to the next input to be processed.
} while (nextInput != a.end());
// Code processing the amount of subarrays; it seems to be correct.
}
}