September 25, 2010
Counting by 2’s
Problem
Write a C++ program to count the number of 2’s between 0 and (n) where (n) is a positive integer.
Solution
We need two loops, one goes from 0 to n and the other one examines the number digit by digit. One way to get the decimal digits of a number is to shift the number to the right. Shifting is nothing but a division by 10. The current digit can be extracted by taking the remainder of the division operation. Here is an example:
1 2 3 4 5 6 7 8 9 10 |
x = 123 d = x%10 = 3 x = x/10 = 12 d = 12%10 = 2 x = x/10 = 1 d = x%10 = 1 x = x/10 = 0 |
This is not an efficient algorithm. In the next article we will solve it in a better way.
Code
Here is the code in C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
//Includes #include <iostream> //STD using namespace std; //Returns number of //2's from 0 to n int NumTwos(int n) { //Total count of 2's int count = 0; //For each number in range for (int i = 0; i <= n; i++) { //Work on a copy of the //numbe because we are //going to change it int x = i; //Keep dividing the number //by 10 until you get 0 while (x != 0) { //The first digit from the //right is the remainder of //the division int d = x%10; //Shift to right by dividing by 10 x = x/10; //If the digit is 2 then //increment the 2's counter if (d == 2) { count++; } } } return count; } //Main function void main() { //Examples cout << NumTwos(1); cout << NumTwos(10); cout << NumTwos(20); cout << NumTwos(30); cout << NumTwos(100); } |