How many ones?

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

How many times does the digit 1 appear in all of the integers from 0 though 999,999?

This simple program less than 30 lines of user written code provides the generalized answer for all appearances of a specified digit between any two integers. And does it in two different ways!

Background & Techniques

I wrote this program to verify the answer I had obtained using pencil and paper. My manual analysis turned out to be wrong.   I had figured that the units position  0 to 9 cycle would occur 100,000 times contributing one "1" each time for 100,000 ones.  Plus there are 10,000 0-9 cycles of the 10's position, adding 10,000 more ones, plus 1000 cycles in the hundreds positions adding 1,000 more, etc. for a total of 111,111 ones between 0 and 999,999.  Wrong!   I'll leave it to the reader to figure what was wrong with my logic either before or after seeing the answer provided by the program.  I figured it out after, which made writing the program worthwhile.

Since only has a few lines of code to do the work of counting, I decided it would be worth posting the program in the "Beginners" category for budding Delphi programmers.   

 Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

TRadiogroup, Calcmethod, selects one of 2 methods to count occurrences of the specified digit with each click of the Searchbtn button.  TSpinedit controls are used to select digit to be tested (Spinedit1.value) and the range on integers over which to test (Spinedit2.value and Spinedit2.value).  A loop over the range to be tested performs the test on each integer using whichever method was selected.  When the loop is complete, a format statement displays the results in a TMemo, Memo2.  

For a given integer N, "Method 1" uses the modulus ("mod") function as "N mod 10" to get the units position digit to test and then uses the integer divide function ("div") to as in "N div 10" in a loop to shift N one digit to the right to test the next digit.  Here is the essential part of the loop for testing an integer N:

while N > 0 do
begin
   if N mod 10 =spinedit1.value then inc(count);

   N:=N div 10;
end;

"Method 2" uses the integer to string ("Inttostr") function to convert each number, I,  to be tested to a string value and then compares each character of the string against a character version of the digit being counted. The code to obtain a character version of the digit to be counted, Spinedit1.value, uses typecasting to add Spinedit1.value to the ordinal value of the character zero, and treats the sum as a character Sdigit.    Here is the code:

{Before the loop get character version of the digit to count}
sdigit:=char(ord('0')+spinedit1.value);

{Inside the loop on I}
s:=inttostr(i); {make string version of integer to test}
for n:=1 to length(s) do if s[n]=sdigit then inc(count)

That's about it. 

 Running/Exploring the Program 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

The fastest way for ranges 0 to 10N-1 is to calculate Nx10N-1.   For other ranges it would still be fastest to use the a version of the formula above.  For example if we identify the count function for digit D between Start and Stop values as F(D,Start,Stop), we could define  occurrences of the digit 3 between 27 and 1432 as if it were something like N(3,0,999) - N(3,0,26) + 4xN(3,0,99) + 3xN(3,0,10)+(3,0,2).  Most of these functions could be evaluated much more quickly than examining each integer in the range.

 

Original:  November 1, 2008

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.