# LINQ and Homework

My daughter asked me to check her homework today.  One of the math problems was:

A book has 352 pages.  How many 4's were used to print all of the page numbers.

She got 35.  She explained how she arrived at that number and while her logic was good, it sounded too low to me.  I started thinking about it a little and then decided I could just write a few lines of C# code to figure out the answer.

As Visual Studio was starting up, I pictured the code in my head: initialize a counter to zero.  Loop through an int from 1 to 352 and see if the ToString() contains a 4.  If so, increase the counter.  Just as I was about to start typing, I thought, "Oh wait – I could do all of this with LINQ!".

`var answer = Enumerable.Range(1, 352).Count(p => p.ToString().Contains("4"));`

How did we ever manage before LINQ?  ;)

Technorati Tags: ,,

• That is cool. I did a similar problem solving a coin problem with my son. couple lines of code then blame. Then I thought, "How fast is Linq" for real world solutions where you may have to do this 100's of time. To my suprise a simple for loop was 20 times faster!!!! I love Linq but I certainly understand that nothing is for free.

• Nice, but I hope your daughter did not submit the output of your expression.

You're counting the pages that have the digit 4 as their page number.

But page 44 for instance has two 4's...

Enumerable.Range(1,352).Sum(p =&gt; p.ToString().Count(c =&gt; c == '4'))

Is uglier but accounts for 44, 144, 244 and 344 (75 total)

• You don't count all 4s in numbers like 144, 244. The correct version is:

Enumerable.Range(1, 352).Sum(p =&gt; p.ToString().ToCharArray().Count(it =&gt; it == '4'))

which gives you 75.

• Unless I misunderstood the question, .Contains does not take into account repeating digits like 44.

var answer = Enumerable.Range(1, 352).Sum((p) => p.ToString().Split('4').Length - 1);

• Could you also give a few words about the mathematical way to do this please? I am curious.

• rajbk/liggett78/Yann,

Good catch!! Totally missed that one. A great thinking question.

• Joining rajnk/liggett78/Yann, but apparently - as I just discovered, I'm not the first one :)

(from number in Enumerable.Range(1, 352)
let regex = new Regex("4")
select regex.Matches(number.ToString()).Count).Sum()

Func answer = (number) => {
int c = 1;
Func scaler = () => (c*=10) / 10;
Func recurse = null;
Func partialAnswer = (n, scale) =>
(n < 4 ? 0 : (n partialAnswer(v.digit, v.scale));
};

• And at last, without recursion:

Func answer = (number) => {
int c = 1;
Func scaler = () => (c*=10) / 10;
Func partialAnswer = (n, scale) =>
(n < 4 ? 0 : (n partialAnswer(v.digit, v.scale));
};

• More clear version using Zip from .NET 4:

Func answer = (number) => {
Func partialAnswer = (n, scale) =>
(n < 4 ? 0 : (n ((int)c) - (int)'0')
.Reverse()
.Zip(Enumerable.Range(0, 10),
(l,r) => new { digit = l, scale = (int) Math.Pow(10,r) })
.Sum(p => partialAnswer(p.digit, p.scale));
};

• Regarding a "mathematical" solution, I think a little bit of logic and reasoning can be used here.

The problem can be solved in two parts.

1) How many times will 4 appear in the "ones" place?
2) How many times will 4 appear in the "tens" place?

1) 352 / 10 = 35 r2 (35 times in the ones place)
Note: r2 49 so we include 340-349
so: 3x10 + 10 extra

1) 35
2) 40
Total: 75

If N = 345
1) 34 r5 -> 34 + 1 = 35
2) 3 r45 -> 30 + 6 = 36
note: 6 gained from 40-45
Total: 71

If N = 429
1) 42 r9 -> 42x1 + 1 = 43
2) 4 r29 -> 4x10 + 0 = 40
3) 0 r429 -> 0x100 + 30 = 30
Total = 113

Summary of the "math":
ones: N = q1 x 10 + r1
n1 = q1
if r1 >= 4, then add one more (n1++)
tens: N = q2 x 100 + r2
where r2 = (a2 x 10 + b2)
n2 = q2 x 10
if a2 > 4, then add 10 (n2 += 10)
if a2 = 4, then add b2+1 (n2 += b2+1)
hundreds: N = q3 x 1000 + r3
where r3 = (a3 x 100 + b3)
n3 = q3 x 100
if a3 > 4, then add 100 (n3 += 100)
if a3 = 4, then add b3+1 (n3 += b3+1)
pattern continues from here...

Total = n1 + n2 + n3 + ...

one last example:
If N = 27348
1) 2734x10 + 8 -> 2734x1 + 1 = 2735
2) 273x100 + 4x10 + 8 -> 273x10 + 9 = 2739
3) 27x1000 + 3x100 + 48 -> 27x100 + 0 = 2700
4) 2x10000 + 7x1000 + 348 -> 2x1000 + 1000 = 3000
5) 0x100000 + 2x10000 + 7348 -> 0x10000 + 0 = 0
Total = 11174

My mathematical code solution:
var totalFours = 0;

//tens
var remainder = pageCount % 10;
var quotient = pageCount / 10;
totalFours += quotient;
if( remainder >= 4 )
totalFours++;

//all other places:
var remainder2 = 0;
var place = 1;
while( quotient > 0)
{
remainder2 = place * remainder + remainder2;
remainder = quotient % 10;
quotient = quotient / 10;
place *= 10;

totalFours += quotient * place;
if( remainder > 4 )
totalFours += place;
else if( remainder == 4 )
totalFours += remainder2 + 1;
}
Console.WriteLine(totalFours);

• A version of the code that merges the "trivial" ones place with the loop that covers all of the other places.

var pageCount = 27348;
var totalFours = 0;
var remainder = 0;
var remainder2 = 0;
var place = 1;
var quotient = pageCount;
while( quotient > 0 )
{
remainder = quotient % 10;
quotient = quotient / 10;

totalFours += quotient * place;
if( remainder > 4 )
totalFours += place;
else if( remainder == 4 )
totalFours += remainder2 + 1;

remainder2 = place * remainder + remainder2;
place *= 10;
}
Console.WriteLine( totalFours );

Cheers.

• Patrick, I bet you never thought your daughter's homework assignment would be this interesting?

Comments have been disabled for this content.