# Find sum of indexes in big list, that satisfies some property

We have this big list of (signed) integers.
We are interested in finding every index "idx" (zero-based, of course) in this list, that has the following property: The sum of the integers preceding (but not including) index idx is equal to the sum of the integers followin (again not including) idx. i.e.: (Referring to our list of integers for a moment as "A[]" and the number of integers in the list N), then we want every index
idx for which the following is true:
A[0] + A[1] + ... + A[idx-1] == A[idx+1] + A[idx+2] ... + A[N-1]

Note that there is likely to be more than one index "idx" in the list that satisfies this property.

Write code that finds every index in our big list that has this property. Then, sum up every index that you found, and that is the answer to question 1. For reference, given the array [-7,1,5,2,-4,3,0], the answer we are looking for is 9 because indices 3 and 6 have the property we are looking for (-7 + 1 + 5 == -4 + 3 + 0 and -7 + 1 + 5 + 2 + -4 + 3 == 0) and 3 + 6 = 9. satisfies this property. Write code that finds every index in our big list that has this property. Then, sum up every index that you found, and that is the answer to question 1.

For reference, given the array [-7,1,5,2,-4,3,0], the answer we are looking for is 9 because indices 3 and 6 have the property we are looking for (-7 + 1 + 5 == -4 + 3 + 0 and -7 + 1 + 5 + 2 + -4 + 3 == 0) and 3 + 6 = 9.

I wrote two variants of code:

### First read the file in std::string, and then parse it in std::list<int>, and finally, count the answer:

#include <iostream>
#include <list>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <sstream>
#include <iterator>
#include <string>
#include <experimental/filesystem>

namespace fs = std::experimental::filesystem;

{
int left_sum = 0;
int right_sum = std::accumulate(list.begin(), list.end(), 0);

uint64_t index_sum = 0;
int curr_index = 0;

std::for_each(list.begin(), list.end(), [&] (int val) {
right_sum -= val;

if(left_sum == right_sum)
index_sum += curr_index;

left_sum += val;

++curr_index;
});

return index_sum;
}

{
if(!fs::exists(file_path))
return "";

std::ifstream infile{file_path.string()};

std::string data{""};

std::string row{""};
while(std::getline(infile, row))
data.append(row);

return data;
}

struct Facet : std::ctype<char>
{
using ParentT = std::ctype<char>;

Facet(std::size_t refs = 0) : ParentT(make_table(), false, refs) {}

{
static int fake = (std::copy(classic_table(), classic_table() + table_size, char_table),
(void)fake, 0);

char_table[','] |= space;

return char_table;
}
};

std::list<int> parse_raw_data(const std::string& raw_data)
{
std::istringstream iss{raw_data};
iss.imbue(std::locale{iss.getloc(), new Facet{}});

std::list<int> data{};

using ISIt = std::istream_iterator<int>;
std::copy(ISIt{iss}, ISIt{}, std::back_inserter(data));

return data;
}

int main()
{
const fs::path DATA_PATH{"data.txt"};

if(raw_data.empty())
{
return 0;
}

std::list<int> data = parse_raw_data(raw_data);

std::cout << "Sum of indexes that satisfies specified propery: " << calc_answer(data) << std::endl;

return 0;
}

### Read it right away in std::list<int>:

#include <iostream>
#include <list>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <sstream>
#include <iterator>
#include <string>
#include <experimental/filesystem>

namespace fs = std::experimental::filesystem;

{
int left_sum = 0;
int right_sum = std::accumulate(list.begin(), list.end(), 0);

uint64_t index_sum = 0;
int curr_index = 0;

std::for_each(list.begin(), list.end(), [&] (int val) {
right_sum -= val;

if(left_sum == right_sum)
index_sum += curr_index;

left_sum += val;

++curr_index;
});

return index_sum;
}

{
if(!fs::exists(file_path))
return std::list<int>{};

std::ifstream infile{file_path.string()};

std::list<int> data{};

std::string number{""};
while(std::getline(infile, number, ','))
data.push_back(std::stoi(number));

return data;
}

int main()
{
const fs::path DATA_PATH{"data.txt"};

if(data.empty())
{
return 0;
}

std::cout << "Sum of indexes that satisfies specified propery: "

return 0;
}

I'm not sure which version of solution is more effective

• Most of the time std::vector is faster than std::list. I don't spot any reason for using std::list here, I could be wrong. The function std::list<int> read_file(const fs::path& file_path) can be changed to bool read_file(const fs::path& file_path, std::list<int> &data) to avoid making a copy. Oct 18, 2017 at 7:44
• "allocation of a solid piece of memory of this size is costly" Not on x64; in any case, if that's your concern then you should be using std::deque; std::list is almost never the right answer. Oct 18, 2017 at 7:57
• Also consider that std::list is going to require 2-3x the memory as std::vector, and the allocations are all going to be very small; in addition to the additional memory consumption, this is terrible for memory fragmentation in real scenarios. Again, never list. ;-] Oct 18, 2017 at 7:59
• Perhaps edit to be a bit more specific on the input format. From reading the code, it appears that you're expecting comma-separated decimal values, perhaps over several lines, and delimited by end-of-file - is that correct? Oct 18, 2017 at 9:58
• @sm4ll_3gg : It consumes a lot of memory since it's node-based; it's slow because it's node-based; and it has exactly zero upsides for this problem. You need a compelling reason to use list, not to avoid it – it's good for solving one or two very specific problems, and you don't have those problems here. Oct 18, 2017 at 10:03

The two-pass algorithm looks like a good choice (although it's unclear why you're using std::list - change that to std::vector or add a comment to justify it).