CODEWITHSUNDEEP
c++algorithm
yoloy
yoloy

Reputation: 161

Task on the number of iterations

There is a number N every iteration it becomes equal to (N*2)-1 I need to find out how many steps the number will be a multiple of the original N;

( 1≤ N ≤ 2 · 10 9 )

For example:

N = 7; count = 0

N_ = 7*2-1 = 13; count = 1; N_ % N != 0

N_ = 13*2-1 = 25; count = 2; N_ % N != 0

N_ = 25*2-1 = 49; count = 3; N_ % N == 0

Answer is 3

if it is impossible to decompose in this way, then output -1

       #include <iostream> 
       using namespace std;

       int main(){
           int N,M,c;
           cin >> N;
           if (N%2==0) {
               cout << -1;
               return 0;
           }
           M = N*2-1;
           c = 1;
           while (M%N!=0){
               c+=1;
               M=M*2-1;
           }
           cout << c;
           return 0;
       }

It does not fit during (1 second limit). How to optimize the algorithm?

P.S All the answers indicated are optimized, but they don’t fit in 1 second, because you need to change the algorithm in principle. The solution was to use Euler's theorem.

Upvotes: 1

Views: 134

Answers (3)

4386427
4386427

Reputation: 44329

There is no doubt that the main problem with your code is signed integer overflow

I added a print of M whenever M was changed (i.e. cout << M << endl;) and gave it the input 29. This is what I got:

57
113
225
449
897
1793
3585
7169
14337
28673
57345
114689
229377
458753
917505
1835009
3670017
7340033
14680065
29360129
58720257
117440513
234881025
469762049
939524097
1879048193
-536870911
-1073741823
-2147483647
1
1
1
1
... endless loop

As you see you have signed integer overflow. That is undefined behavior in C so anything may happen!! On my machine I ended up with a nasty endless loop. That must be fixed before considering performance.

The simple fix is to add a line like

M = M % N;

whenever M is changed. See the answer from @Malek

Besides that you shall also use an unsigned integer, i.e. use uint32_t for all variables.

However, that will not improve performance.

If you still have performance issue after the above fix, you can try this instead:

  uint32_t N;
  cin >> N;
  if (N%2==0) {
    cout << -1;
    return 0;
  }

  // Alternative algorithm
  uint32_t R,c;
  R = 1;
  c = 1;
  while (R != N){
    R = 2*R + 1;
    if (R > N) R = R - N;
    ++c;
  }
  cout << c;

On my laptop this algorithm is 2.5 times faster when testing on all odd numbers in the range 1..100000. However, it might not be sufficient for all numbers in the range 1..2*10^9.

Also notice the use of uint32_t to avoid integer overflow.

Upvotes: 2

Paul Hankin
Paul Hankin

Reputation: 58320

The problem, as other answers have suggested, is equivalent to finding c such that pow(2, c) = 1 mod N. This is impossible if N is even, and possible otherwise (as your code suggests you know).

A linear-time approach is:

int c = 1;
uint64_t m = 2;
while (m != 1){
  c += 1;
  m = (2*m)%N;
}
printf("%d\n", c);

To solve this in 1 second, I don't think you can use a linear-time algorithm. The worst cases will be when N is prime and large. For example 1999999817 for which the above code runs in around 10 seconds on my laptop.

Instead, factor N into its prime factors. Solve 2^c = 1 mod p^k for each prime factor (where p^k appears in the prime factorization of N. Then combine the results using the Chinese Remainder theorem.

When finding the c for a given prime power, if k=1, the solution is c=p-1. When k is larger, the details are quite messy, but you can find a written solution here: https://math.stackexchange.com/questions/1863037/discrete-logarithm-modulo-powers-of-a-small-prime

Upvotes: 5

Malek
Malek

Reputation: 41

The problem is that you're overflowing, the int data type only has 32 bits, and overflows 2^31-1 , in this problem you don't need to keep the actual value of M, you can just keep the modulo of n.

 while (M%N!=0){
           c+=1;
           M=M*2-1;
           M%=N
       }

Edit:In addition, you don't actually need more than N iterations to check if a 0 mod exists, as there are only N different mods to N and it just keeps cycling. so you also need to keep that in mind in case there is no 0 mod.

Upvotes: 4

Related Questions