Cyclic shifts of integer N by another integer m
Given an integer N represented as a binary representation of X = 16 bits. We are also given a number ‘m’ and a character c which is either L or R. The task is to determine a number M that is generated after cyclically shifting the binary representation of N by m positions either left if c = L or right if c = R.
Examples:
Input : N = 7881, m = 5, c = L
Output : 55587
Explanation:
N in binary is 0001 1110 1100 1001 and shifting it left by 5 positions, it becomes 1101 1001 0010 0011 which in the decimal system is 55587.
Input : N = 7881, m = 3, c = R
Output : 9177
Explanation:
N in binary is 0001 1110 1100 1001 and shifted 3 positions to right, it becomes 0010 0011 1101 1001 which in the decimal system is 9177.
Approach:
To solve the problem mentioned above we observe that we have to right shift the number by m if the char is R, else we will do a left shift by m if the char is L where left shifts is equivalent to multiplying a number by 2, right shifts is equivalent to dividing a number by 2.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Cyclic shifts of integer N by another integer m void Count( int N, int m, char turn) { // str represents bitwise representation of N string str = bitset<16>(N).to_string(); m%=( int )str.size(); // rotate the string by a specific count if (turn== 'R' ) str = str.substr(( int )str.size()-m) + str.substr(0,( int )str.size()); else str = str.substr(m) + str.substr(0,m); // printing the number represented by the bitset // in str cout << bitset<16> (str).to_ulong() << '\n' ; } int main() { int N = 7881 ; int m = 5; char turn = 'L' ; Count(N,m,turn); } |
Java
import java.math.*; public class CyclicShift { static int N = 7881 ; static int count = 5 ; static char turn = 'L' ; public static void main(String[] args) { Count(N, count, turn); } static void Count( int N, int count, char turn) { // Convert N into hexadecimal number and // remove the initial zeros in it String N_hex = Integer.toHexString(N); // Convert hexadecimal term binary // string of length = 16 with padded 0s String S = String.format( "%16s" , Integer.toBinaryString(Integer.parseInt(N_hex, 16 ))).replace( ' ' , '0' ); // rotate the string by a specific count count = count % S.length(); if (turn == 'R' ) { S = S.substring(S.length() - count) + S.substring( 0 , S.length() - count); } else { S = S.substring(count) + S.substring( 0 , count); } // Convert the rotated binary string // in decimal form, here 2 means in binary form. System.out.println(Integer.parseInt(S, 2 )); } } |
Python3
# Python implementation to make # Cyclic shifts of integer N by another integer m def Count(N, count, turn): # Convert N into hexadecimal number and # remove the initial zeros in it N = hex ( int (N)).split( 'x' )[ - 1 ] # Convert hexadecimal term binary # string of length = 16 with padded 0s S = ( bin ( int (N, 16 ))[ 2 :] ).zfill( 16 ) # rotate the string by a specific count if (turn = = 'R' ): S = (S[ 16 - int (count) : ] + S[ 0 : 16 - int (count)]) else : S = (S[ int (count) : ] + S[ 0 : int (count)]) # Convert the rotated binary string # in decimal form, here 2 means in binary form. print ( int (S, 2 )) # driver code N = 7881 count = 5 turn = 'L' Count(N, count, turn) |
Javascript
// Javascript code of above approach function Count(N, count, turn) { // Convert N into hexadecimal number and remove the initial zeros in it N = N.toString(16).replace(/^0+/, '' ); // Convert hexadecimal term binary string of length = 16 with padded 0s let S = parseInt(N, 16).toString(2).padStart(16, '0' ); // rotate the string by a specific count if (turn === 'R' ) { S = S.slice(16 - count) + S.slice(0, 16 - count); } else { S = S.slice(count) + S.slice(0, count); } // Convert the rotated binary string in decimal form console.log(parseInt(S, 2)); } // driver code const N = 7881; const count = 5; const turn = 'L' ; Count(N, count, turn); // This code is contributed by princekumaras |
C#
// C# program for the above approach using System; public class CyclicShift { static int N = 7881; static int count = 5; static char turn = 'L' ; public static void Main( string [] args) { Count(N, count, turn); } static void Count( int N, int count, char turn) { // Convert N into hexadecimal number and // remove the initial zeros in it string N_hex = N.ToString( "X" ); // Convert hexadecimal term binary // string of length = 16 with padded 0s string S = Convert.ToString(Convert.ToInt32(N_hex, 16), 2).PadLeft(16, '0' ); // rotate the string by a specific count count = count % S.Length; if (turn == 'R' ) { S = S.Substring(S.Length - count) + S.Substring(0, S.Length - count); } else { S = S.Substring(count) + S.Substring(0, count); } // Convert the rotated binary string // in decimal form, here 2 means in binary form. Console.WriteLine(Convert.ToInt32(S, 2)); } } // This code is contributed by princekumaras |
55587
Time Complexity: O(n)
Auxiliary Space: O(1)