 # MAKEDIV3 - Editorial

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

CAKEWALK

## PREREQUISITES:

Divisibility rules

## PROBLEM:

We need to print an N digit odd number which is divisible by 3 but not divisibility by 9.

## QUICK EXPLANATION:

• If N=1 we ouput 3 else we output 30000\dots03 where the total zeros are N-2.

## EXPLANATION:

Recall that a number is divisible by 3 if the sum of the digits is divisible by 3 and a number is divisible by 9 if the sum of the digits is divisible by 9.

Now, to construct the number, there are many ways to go about it. One such way is as follows:

• If N=1, we just output 3.

• if N \gt 1, we can print a number where the first and last digits equal to 3 and the rest of the digits are equal to 0. The number constructed will be 3000\dots003 . Clearly this number is odd. Also the sum of the digits is 3+3=6 which is divisible by 3 but not divisible by 9. Hence, this number satisifies the required conditions.

## TIME COMPLEXITY:

O(N) for each testcase.

## SOLUTION:

Editorialist's solution
``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
if (i == 1 || i == n)
cout << 3;
else
cout << 0;
}
cout << endl;
}
return 0;
}
``````
Setter's solution
``````//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
void solve()
{
int n;
cin>>n;
string s="";
int sum=0;
for(int i=1;i<=n;i++)
{
sum+=3;
s+='3';
}
if(sum%9==0)
s='9';
cout<<s<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T=1;
cin>>T;
int t=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
``````
Tester's solution
``````#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i = 0; i < n; i++){
if(i == 0 || i == n - 1){
cout<<3;
}else{
cout<<0;
}
}
cout<<"\n";
}
return 0;
}
``````

Please comment below if you have any questions, alternate solutions, or suggestions. 2 Likes

for n==2, 12 is not a valid answer. why is that so?

2 Likes

it’s even and we have to print the odd number only.

Can anyone please tell me why this code is giving WA?
Thanks ``````#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long ll;

int min2(int x, int y) { return x < y ? x : y; }

int max2(int x, int y) { return x > y ? x : y; }

int min3(int x, int y, int z) { return min2(x, min2(y, z)); }

int max3(int x, int y, int z) { return max2(x, max2(y, z)); }

unsigned _power(unsigned val, unsigned _pow = 0)

{

if (_pow <= 0)

return 1;

return val * _power(val, _pow - 1);

}

void solve()

{

int n;

cin >> n;

int a = _power(10, (n - 1));

int b = _power(10, n);

for (int i = a; i < b; i++)

{

if (i % 2 == 1 and i % 3 == 0 and i % 9 != 0)

{

cout << i;

break;

}

}

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

ll t;

cin >> t;

while (t--)

{

solve();

cout << endl;

}

return 0;

}
``````
1 Like

because 12 is not an odd number

Because they want odd number and 12 is not odd.

Why is 1005 not a valid output for N = 4?

It is valid. It satisfies both the conditions of divisibility in the problem

My code is also giving 1005 for N=4 and got accepted too

``````test = int(input())
for i in range(test):
n = int(input())
ans = 10**(n-1) +1

while(ans%3!=0):
ans+=1
if (ans%2==0 or ans%9==0):
ans+=1
continue
print( ans)
``````

What I did was if n is not 1 then the answer will be 10**(n-1) + 5 and for n =1, the answer will be 3.
It will be always odd and will only be divisible by 3 and not 9. I still got WA in this code. Can someone please help to explain what is wrong with this approach?

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
int t;
cin >> t;
while(t–){
int n;
cin >> n;
if(n != 1){
int x = pow(10,n-1) +5;
cout << x << “\n”;
}
else{
cout << 3 << “\n”;
}
}
return 0;
}

Try executing with large input.
N can be as large as 10^4.
I don’t know about c++ but java solution definitely overflows.

I was getting 105 for n=3 and 1005 for n=4 …and both of them are odd numbers of 3 digit and 4 digit divisible by 3 but not by 9…but the compiler kept giving me WA. Please help me and review my code.

MY CODE

1 Like

consider n=100 it will give negative value which means its very large number to calculate power function and gives integer overflow.

2 Likes

If the extreme case is used then power of 10 will be 9999 (for n to be 10^4) means a number with 10000 digits is to be printed and no data type has capacity to store that much large number. Hence , this algorithm is wrong.

1 Like

#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;

``````    if(n%3!=0){
string s1=" ";
for(int i=0;i<n;i++){
s1=s1+"3";
}

cout<<s1<<endl;
}
else{
string s2=" ";
for(int j=0;j<n-1;j++){
s2=s2+"3";
}
s2=s2+"6";

cout<<s2<<endl;
}
``````

}
return 0;
}

thanks!

#include <bits/stdc++.h>
#define int long long int
using namespace std;

int power(int a, int b)
{
if (b == 0)
return 1;
else
return a * power(a, b - 1);
}

int32_t main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n;
cin >> n;
int k=power(10,n) - 7;
cout<<k<<’\n’;
}
return 0;
}

Can someone explain why printing 100…005 is giving me WA ?

#include<bits/stdc++.h>
using namespace std;

int main() {
int tc;
cin>>tc;
for(int i=0;i<tc;i++){
int n;
cin>>n;
int r=pow(10,n-1);
int e=pow(10,n);
if(n==1){
cout<<3<<endl;
}
else{
cout<<r+5<<endl;
}

``````}
return 0;
``````

}
why is this code wrong??? Any 10**n if you add 5 to it it becomes 10000…000005 which is always divisible by 3 but not by 9. Please help.