{"id":25488,"date":"2017-10-15T18:49:37","date_gmt":"2017-10-15T13:19:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25488"},"modified":"2017-10-15T18:49:37","modified_gmt":"2017-10-15T13:19:37","slug":"longest-even-length-substring-sum-first-second-half","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/longest-even-length-substring-sum-first-second-half\/","title":{"rendered":"Longest Even Length Substring such that Sum of First and Second Half is same"},"content":{"rendered":"<p>Given a string \u2018str\u2019 of digits, find length of the longest substring of \u2018str\u2019, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits.<span id=\"more-133264\"><\/span><\/p>\n<p><strong>Examples:<\/strong><\/p>\n<pre>Input: str = \"123123\"\r\nOutput: 6\r\nThe complete string is of even length and sum of first and second\r\nhalf digits is same\r\n\r\nInput: str = \"1538023\"\r\nOutput: 4\r\nThe longest substring with same first and second half sum is \"5380\"\r\n<\/pre>\n<p><strong>Simple Solution [ O(n<sup>3<\/sup>) ]<\/strong><br \/>\nA Simple Solution is to check every substring of even length. The following is C based implementation of simple approach.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">\/\/ A simple C based program to find length of longest  even length<br\/>\/\/ substring with same sum of digits in left and right <br\/>#include&lt;stdio.h&gt;<br\/>#include&lt;string.h&gt;<br\/> <br\/>int findLength(char *str)<br\/>{<br\/>    int n = strlen(str);<br\/>    int maxlen =0;  \/\/ Initialize result<br\/> <br\/>    \/\/ Choose starting point of every substring<br\/>    for (int i=0; i&lt;n; i++)<br\/>    {<br\/>        \/\/ Choose ending point of even length substring<br\/>        for (int j =i+1; j&lt;n; j += 2)<br\/>        {<br\/>            int length = j-i+1;\/\/Find length of current substr<br\/> <br\/>            \/\/ Calculate left &amp; right sums for current substr<br\/>            int leftsum = 0, rightsum =0;<br\/>            for (int k =0; k&lt;length\/2; k++)<br\/>            {<br\/>                leftsum  += (str[i+k]-&#039;0&#039;);<br\/>                rightsum += (str[i+k+length\/2]-&#039;0&#039;);<br\/>            }<br\/> <br\/>            \/\/ Update result if needed<br\/>            if (leftsum == rightsum &amp;&amp; maxlen &lt; length)<br\/>                    maxlen = length;<br\/>        }<br\/>    }<br\/>    return maxlen;<br\/>}<br\/> <br\/>\/\/ Driver program to test above function<br\/>int main(void)<br\/>{<br\/>    char str[] = &quot;1538023&quot;;<br\/>    printf(&quot;Length of the substring is %d&quot;, findLength(str));<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p><strong>Output:<\/strong><\/p>\n<pre>Length of the substring is 4<\/pre>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Longest Even Length Substring such that Sum of First and Second Half is same &#8211; Searching and Sorting &#8211; Given a string \u2018str\u2019 of digits, find length of the longest substring of \u2018str\u2019, such that the length of the substring is 2k digits.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,71670,83550],"tags":[73525,70862,73497,6211,73496,73508,70843,73502,73529,73503,72830,73144,73521,73152,73531,73500,70844,70866,73505,70861,73536,73526,73523,73527,73498,73506,73507,5927,73510,73530,73515,73528,73520,6154,73524,73495,6204,73532,73504,73514,73519,73538,73511,73512,73533,73537,73518,73516,73535,73494,73517,70818,73534,73501,73499,73513,6209,73509,73522],"class_list":["post-25488","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-searching-and-sorting","category-string-length","tag-2-3-in-decimal","tag-array-c-programming","tag-array-example","tag-array-in-java","tag-array-in-programming","tag-array-java","tag-array-programming","tag-array-programming-examples","tag-array-programs-in-java","tag-c-array-example","tag-c-array-length","tag-c-array-programs","tag-c-array-programs-examples","tag-c-program-for-array","tag-c-program-of-array","tag-c-program-using-array","tag-c-programming-array","tag-c-programming-array-examples","tag-c-programming-examples-on-arrays","tag-c-programs-on-arrays","tag-c-array-contains","tag-declare-array-in-java","tag-declare-array-java","tag-example-of-an-array","tag-example-of-array","tag-examples-of-arrays-in-programming","tag-find-out-duplicate-number-between-1-to-n-numbers","tag-how-to-declare-an-array-in-java","tag-how-to-declare-array-in-java","tag-how-to-initialize-array-in-java","tag-initialize-array-java","tag-int-array","tag-int-array-java","tag-java-array","tag-java-array-declaration","tag-java-array-example","tag-java-array-initialization","tag-java-array-methods","tag-java-array-programs","tag-java-array-size","tag-java-array-to-list","tag-java-array-to-set","tag-java-create-array","tag-java-int-array","tag-java-int-size","tag-java-length-of-array","tag-java-new-array","tag-java-print-array","tag-java-return-array","tag-longest-even-length-substring-such-that-sum-of-first-and-second-half-is-same","tag-multidimensional-array-java","tag-n-number","tag-program-for-array","tag-program-of-array","tag-programming-array","tag-string-array-java","tag-two-dimensional-array-in-java","tag-two-dimensional-array-java","tag-what-is-array-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25488","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25488"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25488\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25488"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25488"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25488"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}