Longest Even Length Substring in an array-CodePudding

I solved a problem (Longest Even Length Substring) using a one-dimensional array. But I don't know what is wrong with my code. It is failing. Can you please analyze my code and give me an explanation of why my approach was failing with a proper example.

#include<iostream>
using namespace std;
int main()
 {
    int t;
    string number;
    cin>>t;
    while(t--) {
       cin>>number;
       int current=0,prev=0;
       int length = number.length();
       int sum[length],n1,n2;
       sum[0] = number[0]-'0';
       for(int i=1; i<length; i  ) {
           sum[i] = sum[i-1]   (number[i]-'0');
       }
       for(int i=0; i<length; i  ) {
           for(int j=i 1;j<length;j=j 2) {
             int value;
             if(i==0) value = sum[j]; else value = sum[j]-sum[i-1];
             if(value%2 == 0) {
                 int index = (i j)/2;
                 if(index == 0) {
                     n1 = sum[0];
                     n2 = sum[j];
                 }
                 else {
                  int data;
                  if(i==0) data = 0; else data = sum[i-1];         
                   n1 = sum[index]-data;
                   n2 = sum[j]-sum[index];
                 }
                 if(n1==n2 ){
                     if( (j-1 1) > prev) {
                         prev=current=j-i 1;
                     }
                 }
             }
       }
    }
    cout<<current<<"\n";
}

    return 0;
}

CodePudding user response：

I tried solving this question. It is a simple bruteforce approach. Let me explain my code so that you can understand basic logic and can implement in c by yourself.

Pseudo-code:

Create a list (lst) of numbers from the input number (n) .Here I used map to convert string to integer and then convert it into list.
Create a list (substr) containing all the substrings of the list (lst).
Remove all the substrings from the list (substr) whose length is odd. If length is odd then there is no way in which we can divide the subtring into equal partition (please refer to the question).
Then simply iterate substrings from the list (substr) and divide into two partitions (k1 and k2) and check if there sum are equal.
If they are equal then append the length of the following substring into list (fi).

Then print the max length stored in the list (fi).

for i in range(int(input())):
  n = input()
  lst = list(map(int, n))

  substr = [lst[i: j] for i in range(len(lst))
            for j in range(i   1, len(lst)   1)]

  for i in substr:
      if (len(i) % 2 != 0):
          substr.remove(i)

  fi = []
  for lst1 in substr:
      mid = int(len(lst1)/2)
      k1 = lst1[0:mid]
      k2 = lst1[mid:len(lst1)]
      if(sum(k1) == sum(k2)):
          fi.append(len(lst1))

  if(len(fi) == 0):
     print("0")
  else:
     print(max(fi))

CodePudding user response：

Here you are:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    int t;
    std::cin >> t;
    int i;
    std::string str;
    std::vector<std::vector<int>> px(t);
    for (i = 0; i != t;   i) {
        std::cin >> str;
        px[i].reserve(str.size()   1);
        px[i].emplace_back(0);
        for (auto const& ch : str) {
            px[i].emplace_back(px[i].back()   ch - '0');
        }
    }
    std::vector<int> ans;
    ans.reserve(t);
    int k, k_max, pp, pp_lim, lhs, rhs, tmp, max;
    for (auto const& v : px) {
        max = 0;
        for (k = 1, k_max = (v.size() - 1) >> 1; k <= k_max;   k) {
            for (pp = k, pp_lim = v.size() - k; pp != pp_lim;   pp) {
                lhs = v[pp] - v[pp - k];
                rhs = v[pp   k] - v[pp];
                if (lhs == rhs) {
                    tmp = k << 1;
                    if (tmp > max) {
                        max = tmp;
                    }
                }
            }
        }
        ans.emplace_back(max);
    }
    std::copy(ans.cbegin(), ans.cend(), std::ostream_iterator<int>(std::cout, "\n"));
    return 0;
}

You are trying to implement the prefix sums algorithm but unfortunately you are doing it wrong. Let's take a look at the second str namely "1234123". Its prefix sums will look like that:

0 1 3 6 10 11 13 16

k in this case belongs to the range [1; (8 - 1)/2 or (8 - 1) >> 1], where (8 - 1) is the .size() of "1234123" and 8 is the .size() of v which is the vector that keeps the prefix sums for "1234123". Let's take a look at the sums that we can have:

k = 1

1 = 2 -> v[1] - v[1 - k] = v[1   k] - v[1]
2 = 3 -> v[2] - v[2 - k] = v[2   k] - v[2]
3 = 4 -> v[3] - v[3 - k] = v[3   k] - v[3]
4 = 1 -> v[4] - v[4 - k] = v[4   k] - v[4]
1 = 2 -> v[5] - v[5 - k] = v[5   k] - v[5]
2 = 3 -> v[6] - v[6 - k] = v[6   k] - v[6]

k = 2

1   2 = 3   4 -> v[2] - v[2 - k] = v[2   k] - v[2]
2   3 = 4   1 -> v[3] - v[3 - k] = v[3   k] - v[3]
3   4 = 1   2 -> v[4] - v[4 - k] = v[4   k] - v[4]
4   1 = 2   3 -> v[5] - v[5 - k] = v[5   k] - v[5]

k = 3

1   2   3 = 4   1   2 -> v[3] - v[3 - k] = v[3   k] - v[3]
2   3   4 = 1   2   3 -> v[4] - v[4 - k] = v[4   k] - v[4]

You have a pivot point pp which belongs to the range [k; v.size() - k). Your formula for lhs which is the sum of the characters of the substring of str with k characters on the left of index pp including pp is v[pp] - v[pp - k] and for rhs which is the sum of the characters of the substring of str with k characters on the right of index pp not including pp is v[pp k] - v[pp]. The length of the substring you are processing tmp is always k * 2 or k << 1. You have to compare tmp with max which is the length of the longest substring you have processed so far in v and assign tmp to max If needed. I store the max value for each v in a vector called ans and then output its contents with std::copy.