Interview Problem Notes 3

More notes from Cracking the Coding Interview.

18.4: Counting 2s

Write a method that counts the occurrences of the digit 2 in the integers from 0 through n, inclusive.

Given a positive integer n, return how many times 2 appears among those integers.

This is also an original LeetCode problem, and interviewers like this kind of question.

class Count2 
{
public:
	int countNumberOf2s(int n) 
	{
		int flag = 1;
		int high = 0;
		int low = 0;
		int cur = 0;
		int res = 0;
		while (n / flag)
		{
			low = n - (n / flag)*flag;
			cur = (n / flag) % 10;
			high = n / (flag * 10);
			if (cur < 2)
			{
				res += flag*high;
			}
			else if (cur == 2)
			{
				res += flag*high + low + 1;
			}
			else if (cur > 2)
			{
				res += flag*(high + 1);
			}
			flag *= 10;
		}
		return res;
	}
};

Consider each digit position independently. The same method works for digits 1 through 9; 0 needs special handling, but the idea is identical.

ll countNumberOfxs(ll n,ll x) 
{
	ll flag = 1;
	ll high = 0;
	ll low = 0;
	ll cur = 0;
	ll res = 0;
	while (n / flag)
	{
		low = n - (n / flag)*flag;
		cur = (n / flag) % 10;
		high = n / (flag * 10);
		if (cur < x)
		{
			res += flag*high;
		}
		else if (cur == x)
		{
			res += flag*high + low + 1;
		}
		else if (cur > x)
		{
			res += flag*(high + 1);
		}
		flag *= 10;
	}
	return res;
}

ll countNumberOf0(ll n)
{
	ll flag = 1;
	ll high = 0;
	ll low = 0;
	ll cur = 0;
	ll res = 0;
	while (n / (flag*10))
	{
		low = n - (n / flag)*flag;
		cur = (n / flag) % 10;
		high = n / (flag * 10);
		if (cur == 0)
		{
			res += flag*(high - 1) + low + 1;
		}
		else 
		{
			res += flag*high;
		}
		flag *= 10;
	}
	return res;
}