Check if any value of x can be made equal to k after some operations
Given a number k, the task is to choose a positive number x(any) initially, such that the value of x can be made equal to k after some operations. The operation is to add x to the current score and double the value of x. Note that you need to perform this operation at least twice to change from k to x. Find this positive number x or return -1, if such x does not exist.
Note: Initially the score is 0.
Examples:
Input: k = 7
Output: 1
Explanation: Let’s choose x = 1, Initial score = 0,
Add 1 to score and double x. Therefore, x = 2 ans score = 1
Now add 2 to score and double x. Therefore, x = 4 and score = 3
Now add 4 to the score and double x. Therefore x = 8 and score = 7 which is equal to k.Input: k = 8
Output: -1
Approach: To solve the problem follow the below idea:
This question is observation-based. If we observe the operation the score will be like x + 2x + 4x + 8x + … = k. That means, (2^0)x + (2^1)x +(2^2)x + (2^3)x + … = k, => x ((2^0) + (2^1) +(2^2) + (2^3)) + … = k, => x = k / ((2^0) + (2^1) +(2^2) + (2^3)) + … . Here to compute denominator, we can say that [ ((2^0) + (2^1) +(2^2) + (2^3)) + …] = [(2^4)-1]. This can be computed using the bitwise operation. So, the formula would be (2^0) + (2^1) +(2^2) + (2^3) + … + (2^x) = (2^(x+1)) – 1. Now we need to keep dividing the value by all possible values of x and if k % [(2^x)-1] = 0 means we found the x otherwise return -1. As we need to perform two operations, we can start x from 2 to 31. [(22) to (231)].
Steps that were to follow the above approach:
- Call the function for returning the value of x.
- Run a loop from 22 to 231, to check all the possibilities.
- If found a value of the form 2^x-1, return the answer as k/(2^x-1).
- If not found any such value satisfying our k, return -1 as the answer.
Below is the code to implement the above steps:
C++
// C++ code for the above approach #include <iostream> using namespace std; // Return the desired value of x. long long returnX( int k) { // Check all posibilities from // 2^2 to 2^31 for ( int i = 2; i < 32; i++) { int temp = 1 << i; // 2^i temp--; // 2^i -1 if (k % temp == 0) return k / temp; } return -1; } // Driver's code int main() { int k = 7; // Function Call long long res = returnX(k); cout << res << endl; return 0; } |
Java
// Java code to implement the above approach import java.io.*; import java.util.*; class GFG { public static long returnX( int k) { // Check all posibilities fron 2^2 to 2^31 for ( int i = 2 ; i < 32 ; i++) { int temp = ( int )Math.pow( 2 , i) - 1 ; // 2^i -1 if (k % temp == 0 ) return k / temp; } return - 1 ; } // Driver's code public static void main(String[] args) { int k = 7 ; System.out.println(returnX(k)); } } |
Python3
# Python code to implement the above approach def acceptTheChallenge(k): # Check all posibilities fron 2 ^ 2 to 2 ^ 31 for i in range ( 2 , 32 ): temp = ( 2 * * i) - 1 # 2 ^ i -1 if k % temp = = 0 : return k / / temp return - 1 k = 7 print (acceptTheChallenge(k)) |
Javascript
// javascript code for above approach function acceptTheChallenge(k) { // Check all posibilities fron 2 ^ 2 to 2 ^ 31 for (let i = 2; i <= 31; i++) { let temp = Math.pow(2, i) - 1; // 2 ^ i -1 if (k % temp == 0) { return k / temp; } } return -1; } let k = 7; console.log(acceptTheChallenge(k)); |
C#
// C# code to implement the above approach using System; public class GFG { public static long returnX( int k) { // Check all posibilities fron 2^2 to 2^31 for ( int i = 2; i < 32; i++) { int temp = ( int )Math.Pow(2, i) - 1; // 2^i -1 if (k % temp == 0) return k / temp; } return -1; } // Driver's code public static void Main(String[] args) { int k = 7; Console.WriteLine(returnX(k)); } } // This code contributed by umadevi9616 |
1
Time Complexity: O(N)
Auxiliary Space: O(1)