The algorithm counting the number of numbers in the interval from A to B, the sum of the digits of which are odd?

Hello.
Help students prepare for the Olympic games programming. Apart the solutions to some problems. The solution of one problem, in my opinion not rational. However, to find a more optimal solution I don't.

Problem statement: given two numbers A and B. Count the number of natural numbers on the interval from A to B, the sum of the digits which is even.
The program receives two positive integers A and B not exceeding 10^9, A <= B.
The program should print one integer - the number of natural numbers greater than or equal to A and less than or equal to B, the sum of the digits which is even.

The solution that comes to mind: two loops (loop in loop) - In the first enumerates the numbers themselves, and the second digits of each number.

It is worth considering that the children have to write in a linear programming language (therefore, some decision in principle may not be optimal, but not so much)

I would like to get an idea of how to implement the programme without a second cycle (and maybe first by mathematical calculations), or your thoughts about the algorithm to find numbers whose sum of digits which is even, without busting themselves numbers (if possible).

By the way, it is strange that such numbers doesn't have a name :)

Thanks in advance, Artem.
October 3rd 19 at 02:13
4 answers
October 3rd 19 at 02:15
Solution

On each segment from 10*n to 10*n+9 such numbers exactly 5. Therefore, it is enough to count the number of such segments, and process of boundary segments. Let sumdig(n) - Fonkoze, which gives the remainder from dividing the sum of the digits of n is 2. Then: int s0=(B/10-A/10-1)*5; int s1=(10+sumdig(A/10)-A%10)/2; int s2=(2+B%10-sumdig(B/10))/2; return s0+s1+s2;

October 3rd 19 at 02:17

But if trite (1+B-A)/2 (without a fractional part) ? Sort of converge for small numbers :-)

The point is that the even/odd sums alternates - pearl_Web commented on October 3rd 19 at 02:20
Yes, that's right. Even/odd really alternates, but for numbers without zero. Numbers containing zero fall out of the rotation. - Luciano.Corwin commented on October 3rd 19 at 02:23
Mean set, for example, the 99-100-101? If Yes, so knowing the number of digits and boundary, you can determine the number of these "unaccounted for". Although similar to costal. - pearl_Web commented on October 3rd 19 at 02:26
To identify certainly possible, but it will be the same cycle in the cycle, only with fewer steps. The decision certainly will accelerate the calculation of such numbers, but not sure that will simplify the decision itself. And determining the existence of zero is only possible by iterating over the digits of the number (this is again disadvantage of linear language) - Luciano.Corwin commented on October 3rd 19 at 02:29
Example for A=99 B=10001 will get an incorrect count : 100,300,500,700,900,1000,2000,3000,5000,7000,9000 ie, 2 cycles : - too much number of digits (3,4), determining the appropriate extent of tens (10^2,10^3) in bust of odd options (1*10^x,3*10^x,...) Well, probably,it is possible to optimize the boundaries, but it is, IMHO, extreme savings :-) IMHO, quite easily. A listing of numbers such as do not need (well, except to consider that just overkill) - pearl_Web commented on October 3rd 19 at 02:32
More options with odd sum :-) - pearl_Web commented on October 3rd 19 at 02:35
Maybe I don't quite understand. But the numbers 101, 110, 120, 130... also fall. - Luciano.Corwin commented on October 3rd 19 at 02:38
Exactly. Other ideas yet - pearl_Web commented on October 3rd 19 at 02:41
Although, it is necessary to estimate whether the number of zero falls. Otherwise, I guess you could count their number in the range. - pearl_Web commented on October 3rd 19 at 02:44
I had the idea: each ten (0 to 9) exactly 5 numbers the sum of which is even and the same number with an odd amount. However, each transition to a new ten requires recalculation. And between A and B is not always a whole number of tens. - Luciano.Corwin commented on October 3rd 19 at 02:47
About non-integer - so what's the problem? Round up A dozen more B-less, subtract and multiply by 5 (or something wrong?) And then count cycles of the boundary - pearl_Web commented on October 3rd 19 at 02:50
October 3rd 19 at 02:19

Take a number A, define for him the parity of the sum of numbers, then argue as follows: if A is odd, then A+1 is even, if A is even, then A+1 is odd. Exception is done for the transition xx9 - xy0 (I think there is xx9 and xy0 have odinakovy parity). In General, alternating run to B. I would have done so.

The fact that the numbers with zero within x0y, x0yz also does not fit the alternation. But to find zero number - you need to go through all his numbers - or is there another way?? - pearl_Web commented on October 3rd 19 at 02:22
Here is a good distribute right now. Works int A = 99; int B = 10001; int count1 = 0; int sum = 0; int a = A; while(a != 0) { sum += a % 10; a /= 10; } a = a; bool parity = false; if(sum % 2 == 0) { count1++; parity = true; } while(a < B) { a++; if(a % 10 != 0) parity = !parity; if(parity) count1++; } int count2 = 0; for(int i = A; i <= B; i++) { sum = 0; int temp = i; while(temp != 0) { sum += temp % 10; temp /= 10; } if(sum % 2 == 0) count2++; } Console.WriteLine(count1); Console.WriteLine(count2); Console.ReadLine(); - Luciano.Corwin commented on October 3rd 19 at 02:25
code got eaten by the parser http://pastebin.com/02RRfKaU - pearl_Web commented on October 3rd 19 at 02:28
Thanks for the solution. The code works, but not faster than brute force each number separately. But it is clearly more complicated than the usual brute force. Will look for another solution. - Luciano.Corwin commented on October 3rd 19 at 02:31
I wrote broken crap. Sorry. Above about the "split tens and multiply by five" - IMHO, the best answer. - pearl_Web commented on October 3rd 19 at 02:34
What failed code?? - pearl_Web commented on October 3rd 19 at 02:37
there are generally two checks in the code - one in my way (through alternation) and the other in a blunt two-cycle. Then they are compared. The point is that if we take A = 1, B = 10^7 - does not match the number of numbers (the difference was 1). Began to dig further, but the code is lying after 100. - Luciano.Corwin commented on October 3rd 19 at 02:40
October 3rd 19 at 02:21

Do I understand the conditions of the problem?

Is given an arbitrary range, for example from 2000 to 5000. Need for each number, for example 2013 to add up the numbers, 2 + 0 + 1 + 3 and if the resulting number is even, increment by 1 ?

ie a head-on solution

1) Cycle: created array with the data in the specified range 2) Cycle: number of Disassembled components, folded, divided into two, determined even or odd 3) If even increased the counter to 1 4) Brought the result at the end of the program

The fastest is in this case, the mathematical solution with no cycles, but the school whether it is level?

Tasks of the Olympiad. If you guys are able to understand the essence of the method decisions, then I see no reason this solution does not offer. A variant with a cycle certainly will be considered, but the alternative should be (IMHO). - pearl_Web commented on October 3rd 19 at 02:24

Find more questions by tags MathematicsProgrammingAlgorithms