4

Find sequence of operations to convert 1 to N using Multiply-by-2-Add-1 or Subtr...

 1 year ago
source link: https://www.geeksforgeeks.org/find-sequence-of-operations-to-convert-1-to-n-using-multiply-by-2-add-1-or-subtract-1//
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Find sequence of operations to convert 1 to N using Multiply-by-2-Add-1 or Subtract-1

Given an integer N, the task is to find a sequence of operations to convert 1 to N. You can perform any number of operations, and the goal is to reach the number N using these operations. If it’s not possible to reach N, return -1. There are two possible operations that can be performed on the current number M:

  • Multiply M by 2 and subtract 1 from it.
  • Multiply M by 2 and add 1 to it.

Examples:

Input: N = 17
Output: 2 1 1 1 
Explanation: Operations would be done as follows –

  • Operation 2: 1 -> 2*1+1 = 3
  • Operation 1: 3 -> 2*3-1 = 5
  • Operation 1: 5 -> 2*5-1 = 9
  • Operation 1: 9 -> 2*9-1 = 17

Input: N = 20
Output: -1

Approach: This can be solved with the following idea:

After each operation, the resultant number is odd. So, even numbers cannot be achieved. Consider the binary representation of an integer say “num”:

  • On changing it to 2 * num – 1, the representation changes from …1 to …01.
  • On changing it to 2 * num + 1, the representation changes from …1 to …11.

We know that the binary representation of 1 is simply 1. We also saw that each operation is simply adding either 0 or 1 to the left of the last 1 in the current “num”. So, we can perform the operations in accordance with the binary representation of N.

Steps involved in the implementation of code:

  • If N is even, return -1.
  • Declare a vector V that stores the sequence of operations to convert 1 to N.
  • Declare a flag variable that represents that the operations will be performed as soon as the first 1 is found during the iteration through the binary representation of the given number, i.e. most significant 1.
  • Iterate from i = 29 to 1. It is sufficient for digits up to 10^9.
  • If ith bit from the right is 1, make f=1 and insert 2 into the vector (i.e. 2nd type of operation is performed).
  • Else if the ith bit from the right is 0 and f = 1, insert 1 into the vector (i.e. 1st type of operation is performed).
  • Print the final vector.

Below is the code based on the above approach:

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to Construct N from 1 by
// performing the given operations
// any number of times
void Solve(int N)
{
// If N is even, return -1
if (N % 2 == 0) {
cout << -1;
return;
}
// vector to store the sequence of
// operations
vector<int> V;
// flag variable
int f = 0;
// Iterating through 29 bits
for (int i = 29; i >= 1; i--) {
// If ith bit from right is 1,
// we do second operation
if ((N >> i) & 1) {
f = 1;
V.push_back(2);
}
// Else, do the 1st operation
else if (f) {
V.push_back(1);
}
}
// Print the sequence of operations,
// i.e. elements of the vector
for (auto it : V) {
cout << it << " ";
}
}
// Driver code
int main()
{
int N = 17;
// Function call
Solve(N);
return 0;
}
Output
2 1 1 1

Time Complexity: O(29) ≈ O(1)
Auxiliary Space: O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK