First, (in response to Gururajan) you actually don't need to subtract '0' because the two substrings you're comparing have the same length (IOW the '0' affects both equally). It is good to know how to do this in case it does matter, though.
Probably a little simpler way to do this in O(n^2) is to simply try all even length substrings, and use some preprocessing to compute the required sums in O(1). This is a standard trick, just compute the array of partial sums (e.g. S[0] = 0, S[i] = S[i-1] + A[i-1] for i = 1..n), then the sum of the substring from A[i] to A[j] (inclusive) is just S[j+1] - S[i]. I think what Matteo described should work too, but you have be careful to try all the "slices". Of course there may be a faster way to do this (O(n log n)?) but I couldn't quite come up with it. On Sep 12, 4:33 pm, Matteo Landi <[email protected]> wrote: > Hi guys, > > what do you think about my Python solution (http://ideone.com/nlbdA)? > To solve the problem I used dynamic programming. > > Imagine our input array to be [1, 2, 3, 4, 1, 1], and let's start to > process it from left to right. > > - slice [1]: there is nothing we can do with this slice (winning > slices are supposed to be even). > - slice [1, 2]: there is only one possible sub-sequece to be extracted > from this slice (i.e. [1, 2]), but it is not a winnig one. > - slice [1, 2, 3]: in this case possible slices are [1, 2] and [2, 3]; > the former has been already processed at the previous step; the latter > is obtained shifting the former, and appending the new value '3'; > however, none of them is winning. > - slice [1, 2, 3, 4]: possible slices? [1, 2], [2, 3], [3, 4] and [1, > 2, 3, 4]; again, the slice [3, 4] is obtained shifting [2, 3] and > appending the new value 4. The slice [1, 2, 3, 4] is created from > scratch. None of them is winning. > - slice [1, 2, 3, 4, 1]: possible slices? [1, 2], [2, 3], [3, 4], [4, > 1] ... and [1, 2, 3, 4], [2, 3, 4, 5]; the logic is simple: we need to > take the last slice of the previous step, shift it and append the new > value > - ... > > Are there any better solutions? > > Regards, > Matteo > > > > > > > > > > On Thu, Sep 8, 2011 at 10:30 AM, mukesh kumar <[email protected]> wrote: > > thanks Amahdy& Gururajan , > > > I know Amahdy my code does n't work when the length of substring is > > not equal to length of string. > > > so how can i loop to search the substring in a string , for this i > > have posted my problem. > > > thanks once again for your time. > > > On 9/8/11, Amahdy <[email protected]> wrote: > >> While +Gururajan is correct, u should substract '0', but I recommend > >> substracting it better in the original conversion loop: > > >> for(int k=0 ;k<str1.length();k++) { > >> str[k] =(str1.charAt(k)) - '0'; > > >> One more thing, the problem statement, ur code may work for the sample case > >> but not for others, u assume that the substring length (if exists) is equal > >> to the string length which is not true, for example this test case: 3114, > >> its solution is: 2. > > >> -- > >> Amahdy AbdElAziz > >>www.amahdy.net > >> On Sep 8, 2011 8:02 AM, "Gururajan Raghavendran" <[email protected]> > >> wrote: > >>> You should subtract value 0 from each character of string. > > >>> On Thu, Sep 8, 2011 at 2:18 AM, micke <[email protected]> wrote: > > >>>> Question : > > >>>> write program which takes a single argument. The single argument is a > >>>> string s, which contains only non-zero digits. > >>>> This function should print the length of longest contiguous substring > >>>> of s, such that the length of the substring is 2*N digits and the sum > >>>> of the leftmost N digits is equal to the sum of the rightmost N > >>>> digits.If there is no such string, your function should print 0. > >>>> Sample Test Cases: > > >>>> Input #00: > >>>> 123231 > > >>>> Output #00: > >>>> 6 > > >> ---------------------------------------------------------------------------------------------------------------------------------------------- > >>>> my solution is : > > >>>> public class Str { > >>>> public static void main(String args[]) > >>>> { > > >>>> String str1 = "123231"; > >>>> int[] str = new int[str1.length()]; > >>>> for(int k=0 ;k<str1.length();k++) > >>>> { > >>>> str[k] =(str1.charAt(k)); > >>>> } > > >>>> // int str[] = {1,2,3,2,3,1}; // problem here in > >>>> conversion in this manner > >>>> int len = str.length; > >>>> int sum = 0; > >>>> int sum1 =0; > >>>> for(int i=0;i<(len/2);i++) > >>>> { > >>>> sum = sum+str[i] - '0'; > >>>> } > > >>>> for(int j=(len/2);j<(len);j++) > >>>> { > >>>> sum1 = sum1+str[j] - '0'; > >>>> } > > >>>> if((sum==len)&&(sum1==len)) > >>>> { > >>>> System.out.println(len); > >>>> } > >>>> else > >>>> { > >>>> System.out.println(0); > >>>> } > >>>> } > > >>>> } > > >>>> -- > >>>> You received this message because you are subscribed to the Google Groups > >>>> "google-codejam" group. > >>>> To post to this group, send email to [email protected]. > >>>> To unsubscribe from this group, send email to > >>>> [email protected]. > >>>> For more options, visit this group at > >>>>http://groups.google.com/group/google-code?hl=en. > > >>> -- > >>> You received this message because you are subscribed to the Google Groups > >> "google-codejam" group. > >>> To post to this group, send email to [email protected]. > >>> To unsubscribe from this group, send email to > >> [email protected]. > >>> For more options, visit this group at > >>http://groups.google.com/group/google-code?hl=en. > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "google-codejam" group. > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]. > >> For more options, visit this group at > >>http://groups.google.com/group/google-code?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "google-codejam" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group > > athttp://groups.google.com/group/google-code?hl=en. > > --http://www.matteolandi.net/ -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
