Help in modulo operator

  • Given an integer n, find and return the n’th magic number
  • A magic number is defined as a number which can be expressed as a power of 7 or sum of unique powers of 7
  • First four magic numbers are 7 , 49 , 56 (7 + 49), 343,etc .

i have implemented the solution as follows:
Q8OM0b - Online C++0x Compiler & Debugging Tool - Ideone.com

but it gives me wrong answer,the only difference is that when calculating the value of add we need to apply mod;and the correct solution is as follows:

how will we know where to apply a mod operator…pls help.

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

Also, please provide a link to the original Problem.

1 Like

thnx bro, for informing i have posted the links

1 Like

this is the link to the problem

Thanks, but the link to your submission is private.

is there any other way i can post the link bro

i have updated them.

I’d advise not using std::pow - it’s a floating point operation, and will very likely lead to rounding errors.

3 Likes

but even though i do not use pow it shows wrong answer because in the answer they applied mod while calculating power of 7.how will i know that i should apply mod there.

If there is a danger of integer overflow, and you can apply mod without making the answer wrong, then you should do so.

1 Like

" you can apply mod without making the answer wrong," does this mean that whenever we are asked to find answer modulo some number we can apply mod to every integer useful in calculating answer .

Broadly - if the answer involves adding, multiplying, subtracting (but not dividing) those numbers, then you should be able to apply mod to those numbers.

2 Likes

@anon62013538
The value of pow(7, count) cross the maximum limit of unsigned long long i.e, pow(7, count) > 1e19. Hence, you should use modular power function. Something like this:

ll powmod(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;
}
Your AC Code:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(a) a.begin(), a.end()
#define w(a) cerr << #a << " : " << (a) << "\n";

const ll mod = 1000000007;
ll powmod(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;
}

int main() {  
  ll n;
     cin>>n;
     ll count=1,sum=0;
     while(n>0){
         ll temp=n%2;
          ll add=(powmod(7,count)*temp);
          sum=(sum%mod+add%mod)%mod;
          n/=2;
         count++;
     }
     cout<<sum;
  return 0;
}
Submission overview

1 Like