Modify array by right shifting digits of array elements to values exceeding K
Given an array arr[] of size N and an integer K, the task is to make all array elements > K by performing right shift operations on array elements.
Note: If it is not possible to make all array elements > K, then print -1.
Examples:
Input: arr[] = { 21, 22, 23, 19 }, K = 24
Output: { 26, 26, 27, 25 }
Explanation:
arr[0] = 10101. Performing 1 right shift -→ 11010 → 26
arr[1] = 10110. Performing 3 right shift → 11010 → 26
arr[2] = 10111. Performing 1 right shift → 11011 → 27
arr[3] = 10011. Performing 2 right shift → 11001 → 25Input: arr[] = { 45, 37, 54, 46, 62 }, K = 48
Output: { 54, 50, 54, 53, 62 }
Approach: Follow the steps below to solve the problem :
- Traverse the array
- Perform right shift operation on digits of each array element arr[i].
- If arr[i] > k, update arr[i] and continue.
- If any array element arr[i] ≤ K, then print -1
- Otherwise, print the array arr[].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find// MSB of a numberint setBitNumber(int n){ // Stores the position of the // most significant set bit int k = log2(n); // Return the position of the // most significant set bit return k;}// Function to check if all array// elements are exceeding k or notbool check(int arr[], int k, int n){ // Traverse the array arr for (int i = 0; i < n; i++) { // If current element // does not exceed k if (arr[i] <= k) return false; } return true;}// Function to modify array by// right shifting digits such that// all array elements are exceeding kvoid modifyArray(int arr[], int k, int n){ // Traverse the array for (int i = 0; i < n; i++) { // If current element // exceeds k if (arr[i] > k) continue; else { // Count bits in the binary // representation of arr[i] // MSB of arr[i] int bits = setBitNumber(arr[i]); int el = arr[i]; // Perform right shift operations for (int j = 0; j < bits; j++) { // If the current element is odd if (el & 1) { // Right shift the element el >>= 1; // Perform OR with the bitmask el |= (1 << bits); } // If the current element is even else { // Right shift the element el >>= 1; } // If current element exceeds k if (el > k) { arr[i] = el; break; } } } } // Check if all array elements // are greater than k or not if (check(arr, k, n)) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } else cout << -1;}// Driver Codeint main(){ int arr[] = { 21, 22, 23, 19 }; // Size of array int n = sizeof(arr) / sizeof(arr[0]); int k = 24; modifyArray(arr, k, n); return 0;}// This code is contributed by subhammahato348. |
Java
// Java program to implement// the above approachpublic class GFG{ // Function to find // MSB of a number static int setBitNumber(int n) { // Stores the position of the // most significant set bit int k = (int)(Math.log(n) / Math.log(2)); // Return the position of the // most significant set bit return k; } // Function to check if all array // elements are exceeding k or not static boolean check(int[] arr, int k, int n) { // Traverse the array arr for (int i = 0; i < n; i++) { // If current element // does not exceed k if (arr[i] <= k) return false; } return true; } // Function to modify array by // right shifting digits such that // all array elements are exceeding k static void modifyArray(int[] arr, int k, int n) { // Traverse the array for (int i = 0; i < n; i++) { // If current element // exceeds k if (arr[i] > k) continue; else { // Count bits in the binary // representation of arr[i] // MSB of arr[i] int bits = setBitNumber(arr[i]); int el = arr[i]; // Perform right shift operations for (int j = 0; j < bits; j++) { // If the current element is odd if ((el & 1) != 0) { // Right shift the element el >>= 1; // Perform OR with the bitmask el |= (1 << bits); } // If the current element is even else { // Right shift the element el >>= 1; } // If current element exceeds k if (el > k) { arr[i] = el; break; } } } } // Check if all array elements // are greater than k or not if (check(arr, k, n)) { for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } else System.out.print("-1"); } // Driver code public static void main(String[] args) { int[] arr = { 21, 22, 23, 19 }; // Size of array int n = arr.length; int k = 24; modifyArray(arr, k, n); }}// This code is conntrributed by divyesh072019. |
Python3
# Python program to implement# the above approachimport math# Function to find# MSB of a numberdef setBitNumber(n): # Stores the position of the # most significant set bit k = int(math.log(n, 2)) # Return the position of the # most significant set bit return k# Function to check if all array# elements are exceeding k or notdef check(arr, k): # Traverse the array arr for el in arr: # If current element # does not exceed k if el <= k: return False return True# Function to modify array by# right shifting digits such that# all array elements are exceeding kdef modifyArray(arr, k): # Traverse the array for i in range(len(arr)): # If current element # exceeds k if arr[i] > k: continue else: # Count bits in the binary # representation of arr[i] # MSB of arr[i] bits = setBitNumber(arr[i]) el = arr[i] # Perform right shift operations for j in range(bits): # If the current element is odd if el & 1: # Right shift the element el >>= 1 # Perform OR with the bitmask el |= (1 << bits) # If the current element is even else: # Right shift the element el >>= 1 # If current element exceeds k if el > k: arr[i] = el break # Check if all array elements # are greater than k or not if check(arr, k): return arr else: return -1# Driver Codearr = [21, 22, 23, 19]k = 24print(modifyArray(arr, k)) |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find // MSB of a number static int setBitNumber(int n) { // Stores the position of the // most significant set bit int k = (int)(Math.Log(n, 2)); // Return the position of the // most significant set bit return k; } // Function to check if all array // elements are exceeding k or not static bool check(int[] arr, int k, int n) { // Traverse the array arr for (int i = 0; i < n; i++) { // If current element // does not exceed k if (arr[i] <= k) return false; } return true; } // Function to modify array by // right shifting digits such that // all array elements are exceeding k static void modifyArray(int[] arr, int k, int n) { // Traverse the array for (int i = 0; i < n; i++) { // If current element // exceeds k if (arr[i] > k) continue; else { // Count bits in the binary // representation of arr[i] // MSB of arr[i] int bits = setBitNumber(arr[i]); int el = arr[i]; // Perform right shift operations for (int j = 0; j < bits; j++) { // If the current element is odd if ((el & 1) != 0) { // Right shift the element el >>= 1; // Perform OR with the bitmask el |= (1 << bits); } // If the current element is even else { // Right shift the element el >>= 1; } // If current element exceeds k if (el > k) { arr[i] = el; break; } } } } // Check if all array elements // are greater than k or not if (check(arr, k, n)) { for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } else Console.Write("-1"); } // Driver Code public static void Main() { int[] arr = { 21, 22, 23, 19 }; // Size of array int n = arr.Length; int k = 24; modifyArray(arr, k, n); }}// This code is contributed by chitranayal. |
Javascript
<script>// Javascript program to implement// the above approach// Function to find// MSB of a numberfunction setBitNumber(n){ // Stores the position of the // most significant set bit let k = Math.log2(n); // Return the position of the // most significant set bit return k;}// Function to check if all array// elements are exceeding k or notfunction check(arr, k, n){ // Traverse the array arr for (let i = 0; i < n; i++) { // If current element // does not exceed k if (arr[i] <= k) return false; } return true;}// Function to modify array by// right shifting digits such that// all array elements are exceeding kfunction modifyArray(arr, k, n){ // Traverse the array for (let i = 0; i < n; i++) { // If current element // exceeds k if (arr[i] > k) continue; else { // Count bits in the binary // representation of arr[i] // MSB of arr[i] let bits = setBitNumber(arr[i]); let el = arr[i]; // Perform right shift operations for (let j = 0; j < bits; j++) { // If the current element is odd if (el & 1) { // Right shift the element el >>= 1; // Perform OR with the bitmask el |= (1 << bits); } // If the current element is even else { // Right shift the element el >>= 1; } // If current element exceeds k if (el > k) { arr[i] = el; break; } } } } // Check if all array elements // are greater than k or not if (check(arr, k, n)) { for (let i = 0; i < n; i++) document.write(arr[i] + " "); } else document.write(-1);}// Driver Codelet arr = [ 21, 22, 23, 19 ];// Size of arraylet n = arr.length;let k = 24;modifyArray(arr, k, n);// This code is contributed by subhammahato348.</script> |
Output:
[26, 26, 27, 25]
Time Complexity: O(N)
Auxiliary Space: O(1)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
