Finding all substrings of a given number that are divisible by 11
To find easy to way of Divisibility by 11,
- The multiples of 11: 22, 33, 44, 55, etc. But we did’t easy to find the number 2728, 54695 is divisible by 11.
- Here an easy way to test for divisibility by 11. Take the alternating sum of the digits in the number, read from left to right. If that is divisible by 11, so is the original number.
- So, for example, 2728 has alternating sum of digits 2-7+2-8 = -11. Since -11 is divisible by 11, so is 2728.
- Similarly, for 54695, the alternating sum of digits is 5-4+6-9+5 = 3. This is not divisible by 11, so neither is 54695.
Given a large number, n (having number digits up to 10^6) and various queries of the below form :
- Query(l, r) : find if the sub-string between the indices l and r (Both inclusive) are divisible by 11.
Input
Output
Explanation
- In the first query, 1221 is divisible by 11.
- In the second query, 22 is divisible by 11 and so on.
- We know that any number is divisible by 11 if the difference between sum of odd indexed digits and the sum of even indexed digits is divisible by 11, i.e.,