What's wrong in this approach SQRDSUB. [WA]

I intention are not to spam this discussion forum but I need help. Its hard for to move to the next problem If I haven’t solve the current one. and I’m stuck with this problem and need help.
I’m a new to CP .
in Below I have mention my problem because No one noticing it so I’m asking again.

If you feel I’m spamming the forum just let me know I’ll delete this post.
PS: sorry for my poor english.

1 Like

@shlok_dhara My output is also 3.
see there are 2 odd number and 1 pair odd number so my algo is showing 2+1 = 3.
three is the correct answer. right?
[1], [3], [1,3]

1 Like

Aw sorry I didnt notice let me check some small cases with my code

1 Like
1 Like

I don’t know vijay why u make this problem more complex …it’s easy see my approach and if u find similar to your approach then i think u also figure out where u r going wrong.

MY_SOLUTION

I know the editorial is available but I want to know why my answer is giving me WA in few test Cases.
if you ignore the input loop then Its pretty simple code.
See, first I find the number of odd in array or if any sub Array which has odd in its product.

loop(0, n){
            len = 1;
            if(arr[i]&1) {
                ans++;
                i++;
                while(i < n && arr[i]%2 != 0){
                    ans++;
                    len++;
                    i++;
                }
            }
            ans += (len*(len-1))/2;
        }

Then In another loop I used two pointer technique to find out number divisible 4 and sub Array whose product is divisible by 4.
Also I told you that I put my algorithm in a test case generator and still couldn’t able to find the false test case. I compared my algo with the tester Solution.

aap meri baat smjho mujhe solution nahi chaiye mujhe meri galti pata krna hai. usme meri madad krdo.

Did you find something?

Please help me. I couldn’t able to move to the other problem.

if in a subarray there are 2 numbers which are not divisible by 4 but both are divisible by 2 than that subarray is valid
does your code account for that?

1 Like

I didn’t quite follow your loop for counting subarrays divisible by 4. What is the purpose for :
ans+=n-forward
Can you just tell in brief?

If I get any number which is divisible by 4 (or any subArray ) then any sub array which contain these number will also be divisible by 4.
For example
2 2 6 4 8
here initial two element is divisible by 4, so one pair is [2, 2] and at this instance forward is pointing to the index 1(second element), first(variable) is pointing to the index 0. So n-forward = 4 that means there are 4 pair which will be divisible by 4
[2, 2] and rest 3 are
[2, 2, 6], [2, 2, 6, 4], [2, 2, 6, 4, 8]
This is somewhat works like a two pointer technique.
btw I’m still testing my algorithm with random test generator and tried more than thousands times. and every time my output is same as tester’s Solution given in the editorial.

Yes. I’m strictly checking for that. The number should be divisible by 4.

2 2 3 6 5
what is your output for this?

8

in your code there is this bug
for i=0 foward=1
so for i=n-1 forward=n & arr[forward] will be some garbage value
try to correct this and submit

1 Like

It seems to work fine. But there must be some minute mistake as you’re suggesting too. I’m sorry it looks a little cumbersome to find the issue. I’d suggest you to not be stuck on this for long. As the red coders advise, you should not spend more than 30 minutes on a problem (easy ones); if you can’t think of a solution, just see a hint in editorials.
(Yes, that feeling is great when you finally find the bug. But its a trivial problem and its not worth that much time. I think you can be glad of the fact that the concepts you applied were correct though your approach was different than the one in editorials.)

1 Like

This could be the case but I resolve it by arr[n] = 1;
also I haven’t had any problem while comparing the result in test Case generator.
Thank you for pointing out the bug.

I think you’re right. But I spend almost a week on this problem and to be very honest I sacrifices my night for this. few of my attempt are in the mid night 1:30 AM and because of this I couldn’t able to solve the other problems also. but I think I should give up on this. btw this is pretty straight forward question. still took me this much of time. Really Feeling bad for myself. I will do better next time.