Suppose we have a number N, we have to find a positive number M such that gcd(N^M, N&M) is as large as possible and m < n. We will also return the largest gcd thus obtained.
So, if the input is like 20, then the output will be 31
To solve this, we will follow these steps −
Let us see the following implementation to get better understanding −
from math import gcd, sqrt def bit_count(n): if (n == 0): return 0 else: return (((n & 1) == 0) + bit_count(n >> 1)) def maximum_gcd(n): if (bit_count(n) == 0): for i in range(2, int(sqrt(n)) + 1): if (n % i == 0): return int(n / i) else: val = 0 p = 1 dupn = n while (n): if ((n & 1) == 0): val += p p = p * 2 n = n >> 1 return gcd(val ^ dupn, val & dupn) return 1 n = 20 print(maximum_gcd(n))
20
31