MAKEDIV3 - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

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

DIFFICULTY:

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];
vector <int> adj[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[0]='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. :slight_smile:

3 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.

ahhhh …i misread that… thanks

Can anyone please tell me why this code is giving WA?
Thanks :slight_smile:

#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

2 Likes

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;
}
why this code is giving wrong answer. anyone please explain it

can anyone please help me in finding what’s wrong in my code?
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.