Minimum Array End
Minimum Array End is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise Operations - Power of Two/Four Check subpattern.
Problem statement
Implement Solution.minEnd(n, x) to determine the smallest possible final value of an array of n positive integers.
The array must begin with x, must be strictly increasing, and the bitwise AND of every element must equal x. Bitwise AND compares corresponding binary bits and keeps a bit set only when it is set in every operand.
Return the minimum value that can appear at the last index of such an array. Return only this integer; the array itself does not need to be constructed.
Example 1:
Input: n = 1, x = 13 Output: 13 Explanation: With one element, the array is simply [13], so its final value is 13.
Example 2:
Input: n = 4, x = 10 Output: 15 Explanation: The smallest valid sequence ends with 15; its elements can be 10, 11, 14, and 15, whose bitwise AND is 10.
Example 3:
Input: n = 5, x = 6 Output: 22 Explanation: The zero bits available in 6 are filled in increasing binary order, producing a minimum final value of 22 for five elements.
Constraints:
- n is an integer. - x is an integer. - 1 <= n, x <= 10^4. - The answer fits in a 32-bit signed integer.
Topics and companies
Topics: Bit Manipulation, Array, Math.
How to practise Minimum Array End on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log answer) time and O(1) space.
Open Minimum Array End in the code editor, or read the Minimum Array End editorial for a worked solution with its approach and complexity analysis.
Where Minimum Array End sits in the DSA pattern sheet
- Bit Manipulation Patterns pattern guide
- Bitwise Operations - Power of Two/Four Check subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Minimum Array End
Other problems that use the same Bitwise Operations - Power of Two/Four Check and Bit Manipulation Patterns techniques:
- Bitwise AND of Numbers Range — Medium, same subpattern
- Power of Four — Easy, same subpattern
- Pow(x, n) — Medium, same subpattern
- Counting Bits — Easy, same pattern
- Find the Difference — Easy, same pattern
- Missing Number — Easy, same pattern