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.