HackerRank Number Theory – Strange numbers

Challenge: Strange numbers

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734785

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/strange-numbers/problem

Cerinta

Let $length(A)$ denote the count of digits of a number $A$ in its decimal representation.  
John is looking for new methods of determining which numbers are strange all day long.  
All non-negative numbers of length 1 are strange. Further, a number $X$ with $length(X) \ge1$ can also be considered strange if and only if  

* $X$ is evenly divisible by $length(X)$  
* the number $X/length(X)$ is recursively strange

Your task is to calculate how many strange numbers belong to an interval $[L, R]$.  

**Input Format**  
The first line contains single integer $T$ - the number of test cases. Next $T$ lines contain two integers separated by single space $L$ and $R$.  

**Output Format**  
In $T$ lines, print $T$ integers - count of strange numbers belonging to the interval $[L, R]$.

**Constraints**  
$1 \le T \le 200$  
$0 \le L < R \le 10^{18}$  

**Sample Input**

    5
    7 25
    45 50
    1 100
    99 103
    0 1000000
    
**Sample Output**

    10
    1
    26
    0
    96
    
**Explanation**  
First testcase: There are $10$ strange numbers that belong to the interval $[7,25]$. They are $7,8,9,10,12,14,16,18,20,24$.  
Second testcase: Only $48$ satisfies the given constraints.

Cod sursa

//strange-numbers.cpp
//Strange numbers
//Weekly Challenges - Week 11
//Author: derekhh

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

set<unsigned long long> s;
unsigned long long q[500];
int head, tail;

int lenDigit(unsigned long long num)
{
	int digits = 0; 
	do 
	{ 
		num /= 10; 
		digits++; 
	} while (num != 0);
	return digits;
}

int main()
{
	const long long upperBound = 1000000000000000000LL;
	head = tail = 0;
	for (int i = 0; i <= 9; i++)
	{
		q[tail++] = i;
		s.insert(i);
	}
	while (head < tail)
	{
		unsigned long long num = q[head++];
		int len = lenDigit(num);
		for (int i = len; i <= len + 2; i++)
		{
			unsigned long long candidate = num * i;
			if (s.find(candidate) == s.end() && lenDigit(candidate) == i && candidate <= upperBound)
			{
				q[tail++] = candidate;
				s.insert(candidate);
			}
		}
	}
	int t;
	cin >> t;
	while (t--)
	{
		unsigned long long l, r;
		cin >> l >> r;
		cout << count_if(q, q + tail, [l, r](unsigned long long i) {return i >= l && i <= r; }) << endl;
	}
	return 0;
}