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 <mukesh.wy...@gmail.com> 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 <mrjava.java...@gmail.com> 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" <mail2rg...@gmail.com>
>> wrote:
>>> You should subtract value 0 from each character of string.
>>>
>>> On Thu, Sep 8, 2011 at 2:18 AM, micke <mukesh.wy...@gmail.com> 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 google-code@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> google-code+unsubscr...@googlegroups.com.
>>>> 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 google-code@googlegroups.com.
>>> To unsubscribe from this group, send email to
>> google-code+unsubscr...@googlegroups.com.
>>> 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 google-code@googlegroups.com.
>> To unsubscribe from this group, send email to
>> google-code+unsubscr...@googlegroups.com.
>> 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 google-code@googlegroups.com.
> To unsubscribe from this group, send email to
> google-code+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://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 google-code@googlegroups.com.
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
