Interview Question
Country: India
If the representation is binary then the answer is in combinatorics.
For simplicity, assume [A,B] is the range of all integers with exactly k digits in the binary representations and k is odd. Then your number is choice of (k+1)/2 from k. This would work in general case also when the difference between the sums is c.
You can write a recursive function to recurse [A,B] break it into appropriate ranges and add the sums together, You have to ignore some most importance bits of A in each steps.
Is this a continuous sequence? If yes, then probably I am not understanding the question correctly because for a sequence [A, B];
{ sum(odd) - sum(even) } or vice versa can be 1 only iff its just two numbers in sequence. As soon as we get more than 1 pair of consecutive numbers, the difference will be more than one.
e.g.
{1, 2} = (2) - (1) = 1
{1, 2, 3, 4} = (2+4) - (1+3) = 2
{1, 2, 3, 4, 5, 6} = (2+4+6) - (1+3+5) = 3
And this will be true for any consecutive sequence, not only those who start from 1.
The sums are over the digits in each number in the sequence and not the sequence itself. Example
for sequence of 201,202,..,230
the numbers you are looking for are 210 (2-1+0=1), (220 2-2+0=0) 221 (2-2+1=1) and 230 (2-3+0=-1).
My previous solution would work if we have binary representation of the numbers but it can also work if we have any other representation. basically you can recurs on the number of digits.
if (a0...ak) for all numbers a0=c are in the range find the number of numbers in with k-1 digit where the difference between sum of even and odd digits is equivalent to [c-1,c+1].
Here's a helpful math statement that is easy to prove:
A positive integer number N divides by 11 if and only if (the sum of even place digits of N) - (the sum of odd place digits of N) is a multiple of 11.
Examples: 209, 220, 231, ..., 297, 308, 319, 330, 341, ...
In particular:
If (sum of even place digits) == ( sum of odd place digits) then N divides by 11.
Examples: 220, 231, ..., 297, 330, 341
Note how the more strict criterion leaves out numbers like 209, 308, 319, etc.
Now back to our problem. We can prove the following result
If (sum of even place digits) - ( sum of odd place digits) == 1, then we can prove that N mod 11 == 1, i.e. N is a multiple of 11 + 1.
Proof:
Case 1: If the digit at position 0 (last digit) is not 0, then we can subtract 1 from this digit and get a multiple of 11. So N - 1 == 0 mod 11. Examples: 221, 232, 243, ..
Case 2: If the last digit is 0, but the digit at position 2 is not 0. Then we can subtract 1 from this digit and get a a multiple of 11. So N - 100 = 0 mod 11, or N - (99 + 1) = 0 mod 11. Examples: 320, 430, 540, ...
In the general case, at least one of the even place digits is not 0 (since the sum of the even place digits is greater than the sum of odd place digits). If it's the position 2k, then we subtract 1 from that digit, and we get N - 10^2k = 0 mod 1. But 10^2k = 100^k = (99 +1)^k = 1 mod 11.
Finally, the algorithm is to scan all the numbers N in the range [A,B] such that N = 1 mod 11. Once we find the first such N, the next one is found by adding 11. For each N, we check if (sum of even place digits) - ( sum of odd place digits) == 1. This will filter out numbers like, 309, 408, 507, etc. that don't meet the criterion.
Here's a helpful math statement that is easy to prove:
A positive integer number N divides by 11 if and only if (the sum of even place digits of N) - (the sum of odd place digits of N) is a multiple of 11.
Examples: 209, 220, 231, ..., 297, 308, 319, 330, 341, ...
In particular:
If (sum of even place digits) == ( sum of odd place digits) then N divides by 11.
Examples: 220, 231, ..., 297, 330, 341
Note how the more strict criterion leaves out numbers like 209, 308, 319, etc.
Now back to our problem. We can prove the following result
If (sum of even place digits) - ( sum of odd place digits) == 1, then we can prove that N mod 11 == 1, i.e. N is a multiple of 11 + 1.
Proof:
Case 1: If the digit at position 0 (last digit) is not 0, then we can subtract 1 from this digit and get a multiple of 11. So N - 1 == 0 mod 11. Examples: 221, 232, 243, ..
Case 2: If the last digit is 0, but the digit at position 2 is not 0. Then we can subtract 1 from this digit and get a a multiple of 11. So N - 100 = 0 mod 11, or N - (99 + 1) = 0 mod 11. Examples: 320, 430, 540, ...
In the general case, at least one of the even place digits is not 0 (since the sum of the even place digits is greater than the sum of odd place digits). If it's the position 2k, then we subtract 1 from that digit, and we get N - 10^2k = 0 mod 1. But 10^2k = 100^k = (99 +1)^k = 1 mod 11.
Finally, the algorithm is to scan all the numbers N in the range [A,B] such that N = 1 mod 11. Once we find the first such N, the next one is found by adding 11. For each N, we check if (sum of even place digits) - ( sum of odd place digits) == 1. This will filter out numbers like, 309, 408, 507, etc. that don't meet the criterion.
I don't think there is a better way the checking each number separately.
- Anonymous May 21, 2014