Soluție HackerRank pentru Strange numbers, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Strange numbers
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
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) ≥1 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 ≤ T ≤ 200
0 ≤ L < R ≤ 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 sursă
//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;
}