explain logic

general
1

can anyone explain the apporach used

1 Like
2

It’s all about dynamic programming. If you are not aware of dynamic programming then please try your hand on these problem unless you could not able to crack that logic. On other hand, editorial has already been provided so i suggest you to check out and tell me which line you are having a problem. Author solution is also to the point so overall the editorial and question are clear.

Please check out and comment here after that

3

@akshay29 read the observation part of the editorial,you will get to know what they are trying to say.
They are saying the number is divisible by 6 only if it’s divisible by both 3 and 2.They are checking both for 2 and 3 not just for 3. Hope You get this.

4

yeah sure.Lets see this part in detail.

We have to find number of substrings divisible by 6 and now

1.A number is divisible by 6 only if it’s divisible by both 3 and 2.

2.We can check divisibility by 2 by checking simply (number%2).

3.For a number to be divisible by 3 sum of digits must be divisible by 3.So initially m is set to 0 and every time you traverse a number, take its modulo with 3 adding the part that you have got previously (the previous value of m).This is what (x+m)is doing.
for example say 975 ,for it to be divisible by 3 ,(9+7+5)%3 or (9%3+7%3+5%3) must be divisible by 3 what’s the difference… Like (9%3=0) now m is 0 then comes 7,previous value of m i.e. (0+7)%3 becomes 1 and now comes 5,previous value of m which is now 1,check for (1+5)%3.

Hope You got this now… :slight_smile:

4 Likes
5

m is running sum of digits of substring starting at i . Now if we extend this interval and x is the next digit, then if (x+m)%3==0 and x%2==0 then we can extend the interval and hence we memoize this answer.

m here is just used to remember the sum of last seen substring to check if next substring is super substring or not. So if previous m was 1 and now x is 2 then we have a super substring((1+2)%3==0 &&2 is even).

Had we not memoized m then we would have to find the running sum of subset again which will blow up the time constraints.

Hope this helps

6

Compute all the subarrays. Refer Link

Now for each subarray check its divisibility by 2 and 3. If number is even then it is divisible by 2 and if sum of all elements of substring is divisible by 3 the substring is divisible by 3. Also don’t forget to count presence of zero in substring.

Hope it Helps.

7

@bansal1232 i know dynamic programming but still i m not able understand. https://www.hackerrank.com/rest/contests/hourrank-18/challenges/super-six-substrings/hackers/gvaibhav21/download_solution.
if((s[i]-‘0’)%2 ==0)
ans += cnt[presum%3];
if(i+1 == n || s[i+1] != ‘0’)
cnt[presum%3]++;
if(s[i]==‘0’)
ans++;

if 1,2 is the remainder by taking modulous by 3 then how it is divisble by 6.

1 Like
8

Even I cant get that “(x+m)%3” thing in the function. Waiting for an answer now lol XD

9

You’re right here, but can you explain the " “(x+m)%3” thing in the function." ??

10

Good explanation, but regarding remainder I got 1 query.

We know that if we are getting remainder of, lets say 2 when we divide 5 by 3.

Then its a sure fact that (5-2)%3=0. Meaning, number - remainder would be surely divisible.

So why are we doing addition in form of (x+m) instead of using subtraction property I wrote about above. I would appreciate if you can help me here :slight_smile:

11

We are traversing every number and starting for index i of string and checking if its divisible by 3 and 2.

Lets say 975 first we will check every possible case In this case for (9,97,975) which start at index 0 then for cases which start at index 1 (7,75) and then cases which start at index 2 i.e 5 in total 6 cases
9,97,975,7,75,5.For your query i.e.“Then its a sure fact that (5-2)%3=0. Meaning, number - remainder would be surely divisible.” We are storing it to check for the next digit of string (Remember we have to check ever substring of the given string)
Hope you got this :slight_smile:

1 Like
12

I think I need a bit more practice of dynamic programming to truly appreciate what you say. I am getting it, but there are multiple ‘whys’ and ‘ifs’ which can be best resolved by a future attempt with a much more refined skill in dp. Thanks for your effort and explanation dear :slight_smile:

1 Like
13

What if x is not two but some other remainder like 0 or 1?

14

@naksh9619 Asking for mark is not a good way. It seems that you are helping the people only because of earning karma points.