Data Modelling & AI Data Structure & Algorithm

Modify array by right shifting digits of array elements to values exceeding K

23 June 2025

0

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 → 25

Input: 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 number
int 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 not
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
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) {
 
                    // 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 Code
int 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 approach
public 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 approach
import math
 
# Function to find
# MSB of a number
def 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 not
def 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 k
def 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 Code
 
arr = [21, 22, 23, 19]
k = 24
 
print(modifyArray(arr, k))

C#

// C# program to implement
// the above approach
using 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 number
function 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 not
function 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 k
function 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 Code
let arr = [ 21, 22, 23, 19 ];
 
// Size of array
let 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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Modify array by right shifting digits of array elements to values exceeding K

C++

Java

Python3

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

LEAVE A REPLY Cancel reply

Most Popular

iOS 27 Vs. Android 17 reveals a LOT. [Video]

Your Pixel phone could get a big under-the-hood upgrade this year

Android 17 QPR1 Beta 6 hits Pixel phones with a major milestone for developers

Samsung’s Galaxy S27 Pro could finally fix what was wrong with the Plus

EDITOR PICKS

iOS 27 Vs. Android 17 reveals a LOT. [Video]

Your Pixel phone could get a big under-the-hood upgrade this year

Android 17 QPR1 Beta 6 hits Pixel phones with a major milestone for developers

POPULAR POSTS

iOS 27 Vs. Android 17 reveals a LOT. [Video]

Your Pixel phone could get a big under-the-hood upgrade this year

Android 17 QPR1 Beta 6 hits Pixel phones with a major milestone for developers

POPULAR CATEGORY

ABOUT US

FOLLOW US