{"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[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20simple%20C%20based%20program%20to%20find%20length%20of%20longest%20%20even%20length%0A%2F%2F%20substring%20with%20same%20sum%20of%20digits%20in%20left%20and%20right%20%0A%23include%3Cstdio.h%3E%0A%23include%3Cstring.h%3E%0A%20%0Aint%20findLength(char%20*str)%0A%7B%0A%20%20%20%20int%20n%20%3D%20strlen(str)%3B%0A%20%20%20%20int%20maxlen%20%3D0%3B%20%20%2F%2F%20Initialize%20result%0A%20%0A%20%20%20%20%2F%2F%20Choose%20starting%20point%20of%20every%20substring%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Choose%20ending%20point%20of%20even%20length%20substring%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3Di%2B1%3B%20j%3Cn%3B%20j%20%2B%3D%202)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20length%20%3D%20j-i%2B1%3B%2F%2FFind%20length%20of%20current%20substr%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Calculate%20left%20%26%20right%20sums%20for%20current%20substr%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20leftsum%20%3D%200%2C%20rightsum%20%3D0%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20k%20%3D0%3B%20k%3Clength%2F2%3B%20k%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20leftsum%20%20%2B%3D%20(str%5Bi%2Bk%5D-\u20180\u2019)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rightsum%20%2B%3D%20(str%5Bi%2Bk%2Blength%2F2%5D-\u20180\u2019)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20result%20if%20needed%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(leftsum%20%3D%3D%20rightsum%20%26%26%20maxlen%20%3C%20length)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maxlen%20%3D%20length%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20maxlen%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(void)%0A%7B%0A%20%20%20%20char%20str%5B%5D%20%3D%20%221538023%22%3B%0A%20%20%20%20printf(%22Length%20of%20the%20substring%20is%20%25d%22%2C%20findLength(str))%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Length of the substring is 4<\/pre>\n[ad type=\u201dbanner\u201d]\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}]}}