문제 링크

내 코드

결국 못 풀었다. 위에 3개는 Solution 참고..

마지막으로 실패한 코드

// n = 3, x = 4
// 100, 101, 110, 111 => 4
// 1100, 1101, 1110, 1111 => 4

// n = 2, x = 7
// 111 => 1
// 1111 => 1
// 11111 => 1

class Solution {
public:
	long long minEnd(int n, int x) {
		// array of positive integers nums of size n
		// where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i].
		// bitwise AND operation between all elements of nums is x.

		// 100,000,000
		int tmp = x, cnt{}, len{};
		while (tmp) {
			if (!(tmp & 1)) ++cnt;
			tmp >>= 1;
			++len;
		}

		long long cntLessThanX = (1 << cnt);

        long long answer = x;
		// x를 cnt + 1로 나누기.
		// 나눈 몫만큼 앞에 1추가
		if (n % cntLessThanX) {
			if (cntLessThanX != 1 && n / cntLessThanX) answer |= ((n / cntLessThanX) << len);
			else if (cntLessThanX == 1 && n / cntLessThanX) answer |= ((n / cntLessThanX) - 1 << len);
		}

		// 나눈 나머지만큼 추가 개수 확인
		for (int i{}, chk{}; ; ++i) {
			if (((answer + i) & x) == x) ++chk;

			if (chk == n % cntLessThanX || chk == cntLessThanX) {
				answer += i;
				break;
			}
		}

		return answer;
	}
};

Solution

Approach 1: Consecutive ORing

• 1730ms, 8.4MB
• Complexity
  • Let $n$ be the number of iterations required, which is determined by the input size of $n$.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    long long minEnd(int n, int x) {
        long long result = x;

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

        return result;
    }
};

이런 식으로도 갱신이 가능하구나.. (단순히 다 도는 경우 시간초과 발생.)

Approach 2: Bit Manipulation and Binary Construction

• 0ms, 9.4MB
• Complexity
  • Time Complexity: $O(\log n)$
  • Space Complexity: $O(\log n)$

#define ll long long

class Solution {
public:
    long long minEnd(int n, int x) {
        ll result = 0, bit;
        // Reducing n by 1 to exclude x from the iteration
        --n;

        // Step 1: Initialize vectors to hold the binary representation of x and
        // n-1
        vector<int> binaryX(64, 0);  // Binary representation of x
        vector<int> binaryN(64, 0);  // Binary representation of n-1

        ll longX = x;  // Convert x to long long for 64-bit manipulation
        ll longN = n;  // Convert n-1 to long long for 64-bit manipulation

        // Step 2: Build binary representations of x and n-1
        for (int i = 0; i < 64; ++i) {
            bit = (longX >> i) & 1;  // Extract i-th bit of x
            binaryX[i] = bit;

            bit = (longN >> i) & 1;  // Extract i-th bit of n-1
            binaryN[i] = bit;
        }

        int posX = 0, posN = 0;

        // Step 3: Combine binary representation of x and n-1
        while (posX < 63) {
            // Traverse binaryX until we find a 0 bit
            while (binaryX[posX] != 0 && posX < 63) {
                ++posX;
            }
            // Copy bits from binaryN (n-1) into binaryX (x) starting from the
            // first 0
            binaryX[posX] = binaryN[posN];
            ++posX;
            ++posN;
        }

        // Step 4: Rebuild the final result from the combined binary
        // representation
        for (int i = 0; i < 64; ++i) {
            if (binaryX[i] == 1) {
                // convert binary bit to decimal value
                result += pow(2, i);
            }
        }

        return result;
    }
};

Approach 3: Bitmasking with Logical Operations

• 0ms, 8.6MB
• Complexity
  • Time Complexity: $O(\log n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    long long minEnd(int n, int x) {
        long long result = x, 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;
    }
};