B. Fair Numbers | Codeforces | Technocup 2021 - Elimination Round 3 | Solution
raunit - in CodingWe call a positive integer number fair if it is divisible by each of its nonzero digits. For example, 102 is fair (because it is divisible by 1 and 2 ), but 282 is not, because it isn't divisible by 8 . Given a positive integer π . Find the minimum integer π₯ , such that πβ€π₯ and π₯ is fair.
B. Fair Numbers
Time limit per test: 2 seconds
Memory limit per test: 256 megabytes
Problem Statement
We call a positive integer number fair if it is divisible by each of its nonzero digits.
For example, 102
is fair (because it is divisible by 1
and 2
),
but 282
is not, because it isn't divisible by 8
.
Given a positive integer n
, find the minimum integer x
, such that n β€ x
and x
is fair.
Input
The first line contains an integer t
(1 β€ t β€ 10Β³
), the number of test cases.
Each of the next t
lines contains an integer n
(1 β€ n β€ 10ΒΉβΈ
).
Output
For each test case, print a single integer β the least fair number, which is not less than n
.
Example
Input
4 1 282 1234567890 1000000000000000000
Output
1 288 1234568040 1000000000000000000
Note
Explanations for some test cases:
- In the first test case, number
1
is fair itself. - In the second test case, number
288
is fair (it's divisible by both2
and8
). None of the numbers from [282,287
] is fair.
Hint
A super-fair number is a number that is divisible by every digit from 1
to 9
.
Since these numbers are also divisible by the least common multiple: LCM(1..9) = 2520
, we can use this
property to optimize our search. Instead of checking every number sequentially,
we increment n
until we find a number that is divisible by all its nonzero digits.
This guarantees that our answer wonβt exceed the nearest super-fair number.
bool helper2(int n){
string s = to_string(n);
for(auto c:s){
int i = c-'0';
if(i>0){
if(n%i!=0)return false;
}
}
return true;
}
void solve() {
int n;
cin>>n;
while(true){
if( helper2(n)){
cout<<n<<endl;
return;
}
n++;
if(n%2520 == 0){
cout<<n<<endl;
return;
}
}
}
Solution Explanation
The goal is to find the smallest fair number x
such that x β₯ n
and x
is divisible by all of its nonzero digits.
The solution uses a brute-force approach with an important optimization.
Checking Fairness
The helper2(n)
function determines if a number is fair:
- Convert
n
into a string and iterate over its digits. - Ignore
0
to avoid division errors. - If any nonzero digit does not divide
n
evenly, returnfalse
. - If all nonzero digits divide
n
, returntrue
.
Finding the Smallest Fair Number
The algorithm starts from n
and increments it until it finds a fair number.
- If
n
is fair, print it and return. - Otherwise, increment
n
and check again. - If
n
becomes a multiple of2520
(the LCM of 1 to 9), print it immediately.
Optimization Using LCM
Since every **super-fair number** is divisible by **2520**, the algorithm is optimized by checking if n
is a multiple of 2520
:
- If
n
reaches a multiple of2520
, we print it immediately. - This skips unnecessary iterations and speeds up the solution.
Time Complexity
- In the worst case, the algorithm increments n
a few times until it finds a fair number.
- Thanks to the 2520
optimization, it runs efficiently for large values of n
.
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define F first
#define S second
#define pb push_back
#define si set <int>
#define vi vector <int>
#define pii pair <int, int>
#define vpi vector <pii>
#define vpp vector <pair<int, pii>>
#define mii map <int, int>
#define mpi map <pii, int>
#define spi set <pii>
#define endl "\n"
#define sz(x) ((int) x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue <int>
#define que_min priority_queue <int, vi, greater<int>>
#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a) for(auto x : a) cout << x << " "; cout << endl
#define print1(a) for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y) for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
#define scanit(a,n) for(ll indexaa=0; indexaa<n; indexaa++) cin>>a[indexaa];
inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1) x *= a;
a *= a;
b >>= 1;
}
return x;
}
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
const int N = 200005;
bool helper2(int n){
string s = to_string(n);
for(auto c:s){
int i = c-'0';
if(i>0){
if(n%i!=0)return false;
}
}
return true;
}
void solve() {
int n;
cin>>n;
while(true){
if( helper2(n)){
cout<<n<<endl;
return;
}
n++;
if(n%2520 == 0){
cout<<n<<endl;
return;
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t z = clock();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
raunit
Technical Writer at CodingKaro