Given an integer x. The task is to convert x to the form 2n – 1 by performing the following operations in the specified order on x:
- You can select any non-negative integer n and update x = x xor (2n – 1)
- Replace x with x + 1.
The first applied operation must be of a first type, the second of the second type, the third again of the first type, and so on. Formally, if we number the operations from one in the order they are executed, then odd-numbered operations must be of the first type and the even-numbered operations must be of the second type. The task is to find the number of operations required to convert x to the form 2n – 1.
Examples:
Input: x = 39
Output: 4
Operation 1: Pick n = 5, x is transformed into (39 xor 31) = 56.
Operation 2: x = 56 + 1 = 57
Operation 3: Pick n = 3, x is transformed into (57 xor 7) = 62.
Operation 4: x = 62 + 1 = 63 i.e. (26 – 1).
So, total number of operations are 4.
Input: x = 7
Output: 0
As 23 -1 = 7.
So, no operation is required.
Approach: Take the smallest number larger than x which is of the form of 2n – 1 say num, then update x = x xor num and then x = x + 1 performing two operations. Repeat the step until x is of the form 2n – 1. Print the number of operations performed in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAX = 24;// Function to return the count// of operations requiredint countOp(int x){ // To store the powers of 2 int arr[MAX]; arr[0] = 1; for (int i = 1; i < MAX; i++) arr[i] = arr[i - 1] * 2; // Temporary variable to store x int temp = x; bool flag = true; // To store the index of // smaller number larger than x int ans; // To store the count of operations int operations = 0; bool flag2 = false; for (int i = 0; i < MAX; i++) { if (arr[i] - 1 == x) flag2 = true; // Stores the index of number // in the form of 2^n - 1 if (arr[i] > x) { ans = i; break; } } // If x is already in the form // 2^n - 1 then no operation is required if (flag2) return 0; while (flag) { // If number is less than x increase the index if (arr[ans] < x) ans++; operations++; // Calculate all the values (x xor 2^n-1) // for all possible n for (int i = 0; i < MAX; i++) { int take = x ^ (arr[i] - 1); if (take <= arr[ans] - 1) { // Only take value which is // closer to the number if (take > temp) temp = take; } } // If number is in the form of 2^n - 1 then break if (temp == arr[ans] - 1) { flag = false; break; } temp++; operations++; x = temp; if (x == arr[ans] - 1) flag = false; } // Return the count of operations // required to obtain the number return operations;}// Driver codeint main(){ int x = 39; cout << countOp(x); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG{static int MAX = 24;// Function to return the count// of operations requiredstatic int countOp(int x){ // To store the powers of 2 int arr[] = new int[MAX]; arr[0] = 1; for (int i = 1; i < MAX; i++) arr[i] = arr[i - 1] * 2; // Temporary variable to store x int temp = x; boolean flag = true; // To store the index of // smaller number larger than x int ans =0; // To store the count of operations int operations = 0; boolean flag2 = false; for (int i = 0; i < MAX; i++) { if (arr[i] - 1 == x) flag2 = true; // Stores the index of number // in the form of 2^n - 1 if (arr[i] > x) { ans = i; break; } } // If x is already in the form // 2^n - 1 then no operation is required if (flag2) return 0; while (flag) { // If number is less than x increase the index if (arr[ans] < x) ans++; operations++; // Calculate all the values (x xor 2^n-1) // for all possible n for (int i = 0; i < MAX; i++) { int take = x ^ (arr[i] - 1); if (take <= arr[ans] - 1) { // Only take value which is // closer to the number if (take > temp) temp = take; } } // If number is in the form of 2^n - 1 then break if (temp == arr[ans] - 1) { flag = false; break; } temp++; operations++; x = temp; if (x == arr[ans] - 1) flag = false; } // Return the count of operations // required to obtain the number return operations;} // Driver code public static void main (String[] args) { int x = 39; System.out.println(countOp(x)); }}// This code is contributed by anuj_67.. |
Python3
# Python3 implementation of the approach MAX = 24; # Function to return the count # of operations required def countOp(x) : # To store the powers of 2 arr = [0]*MAX ; arr[0] = 1; for i in range(1, MAX) : arr[i] = arr[i - 1] * 2; # Temporary variable to store x temp = x; flag = True; # To store the index of # smaller number larger than x ans = 0; # To store the count of operations operations = 0; flag2 = False; for i in range(MAX) : if (arr[i] - 1 == x) : flag2 = True; # Stores the index of number # in the form of 2^n - 1 if (arr[i] > x) : ans = i; break; # If x is already in the form # 2^n - 1 then no operation is required if (flag2) : return 0; while (flag) : # If number is less than x increase the index if (arr[ans] < x) : ans += 1; operations += 1; # Calculate all the values (x xor 2^n-1) # for all possible n for i in range(MAX) : take = x ^ (arr[i] - 1); if (take <= arr[ans] - 1) : # Only take value which is # closer to the number if (take > temp) : temp = take; # If number is in the form of 2^n - 1 then break if (temp == arr[ans] - 1) : flag = False; break; temp += 1; operations += 1; x = temp; if (x == arr[ans] - 1) : flag = False; # Return the count of operations # required to obtain the number return operations; # Driver code if __name__ == "__main__" : x = 39; print(countOp(x)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{ static int MAX = 24;// Function to return the count// of operations requiredstatic int countOp(int x){ // To store the powers of 2 int []arr = new int[MAX]; arr[0] = 1; for (int i = 1; i < MAX; i++) arr[i] = arr[i - 1] * 2; // Temporary variable to store x int temp = x; bool flag = true; // To store the index of // smaller number larger than x int ans = 0; // To store the count of operations int operations = 0; bool flag2 = false; for (int i = 0; i < MAX; i++) { if (arr[i] - 1 == x) flag2 = true; // Stores the index of number // in the form of 2^n - 1 if (arr[i] > x) { ans = i; break; } } // If x is already in the form // 2^n - 1 then no operation is required if (flag2) return 0; while (flag) { // If number is less than x increase the index if (arr[ans] < x) ans++; operations++; // Calculate all the values (x xor 2^n-1) // for all possible n for (int i = 0; i < MAX; i++) { int take = x ^ (arr[i] - 1); if (take <= arr[ans] - 1) { // Only take value which is // closer to the number if (take > temp) temp = take; } } // If number is in the form of 2^n - 1 then break if (temp == arr[ans] - 1) { flag = false; break; } temp++; operations++; x = temp; if (x == arr[ans] - 1) flag = false; } // Return the count of operations // required to obtain the number return operations;}// Driver codestatic public void Main (){ int x = 39; Console.WriteLine(countOp(x));}}// This code is contributed by ajit. |
Javascript
<script>// Javascript implementation // of the approachconst MAX = 24;// Function to return the count// of operations requiredfunction countOp(x){ // To store the powers of 2 let arr = new Array(MAX); arr[0] = 1; for (let i = 1; i < MAX; i++) arr[i] = arr[i - 1] * 2; // Temporary variable to store x let temp = x; let flag = true; // To store the index of // smaller number larger than x let ans; // To store the count of operations let operations = 0; let flag2 = false; for (let i = 0; i < MAX; i++) { if (arr[i] - 1 == x) flag2 = true; // Stores the index of number // in the form of 2^n - 1 if (arr[i] > x) { ans = i; break; } } // If x is already in the form // 2^n - 1 then no operation is // required if (flag2) return 0; while (flag) { // If number is less than x // increase the index if (arr[ans] < x) ans++; operations++; // Calculate all the values // (x xor 2^n-1) // for all possible n for (let i = 0; i < MAX; i++) { let take = x ^ (arr[i] - 1); if (take <= arr[ans] - 1) { // Only take value which is // closer to the number if (take > temp) temp = take; } } // If number is in the form of // 2^n - 1 then break if (temp == arr[ans] - 1) { flag = false; break; } temp++; operations++; x = temp; if (x == arr[ans] - 1) flag = false; } // Return the count of operations // required to obtain the number return operations;}// Driver code let x = 39; document.write(countOp(x));</script> |
Output:
4
Time Complexity: O(MAX*N)
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
