minimum End Value [Bit manip]

XXX. Minimize End Value

Bit Manipulation

Iteration

Problem Statement:

Given an integer n (number of iterations) and an integer x, minimize the end value of a sequence by performing either a bitwise OR operation or incrementing the value based on specific conditions.

Algorithm:

Approach 1: Iterative Increment and Bitwise OR

1. Initialize the current value to x.
2. Iterate n-1 times, performing the following operations:
• Increment the current value.
• Perform a bitwise OR with x.

Approach 2: Optimized Bit Manipulation

1. Initialize the result to x and prepare a mask starting at 1.
2. Iterate over each bit position of x:
• If the bit in x is 0, update the result by setting the bit based on the least significant bit of n.
• Shift n to the right by 1 for the next iteration.
• Shift the mask to the left for the next bit position.
3. Continue until all relevant bits of n are processed.

Complexity:

Time Complexity: O(log(n)), since we process each bit of n in the optimized approach.
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

public class Solution {
    // Approach 1: Iterative Increment and Bitwise OR
    public long minEndOld(int n, int x) {
        long curr = x;

        // Step 1: Iterate n-1 times (since we already initialized result with x)
        while (--n > 0) 
            // Step 2: Increment result and perform bitwise OR with x
            curr = (curr + 1) | x;
        
        return curr;
    }

    // Approach 2: Optimized Bit Manipulation
    public long minEnd(int n, int x) {
        long result = x;
        long mask;
        n--; // Reducing n by 1 to exclude x from the iteration

        // Step 1: Iterate over each bit position with mask starting at 1 and shifting left
        for (mask = 1; n > 0; mask <<= 1) {
            // Step 2: If the corresponding bit in x is 0
            if ((mask & x) == 0) {
                // Set the bit in result based on the least significant bit of n
                result |= (n & 1) * mask;
                // Shift n to the right by 1 to process the next bit
                n >>= 1;
            }
        }

        return result;
    }
}