3133. Minimum Array End
給兩個整數n、x
要建立一個長度為n的正整數矩陣:nums
其中nums[i+1]>nums[i]
最後nums的所有元素經過 AND 操作後會等於x
請問最小的nums[n-1]為多少
思路:
因為 AND 操作後要等於x所以nums[0]=x
x用二進位表示後的為1的bits
nums裡所有的元素那些bits也都要是1
EX : x = 6 = 0b110
那nums裡所有元素的bit1、2都要是1
要求最小的nums[n-1]
就把n-1換成2進位，接著把n-1所有的bits塞到x為0的bits裡就是答案
EX : x = 4 = 0b100 、 n=5 -> n-1 = 4 = 0b100
nums[n-1] = 0b1100 = 12
C code :
long long minEnd(int n, int x) {
long long n_long = (long long)(n)-1 , x_long = (long long)(x) ;
int idx = 0 ;
while( n_long > 0 )
{
while( ( x_long & ( 1LL << idx ) ) > 0 )
{
idx++;
}
x_long |= ( ( n_long & 1 ) << idx );
idx++;
n_long >>= 1;
}
return x_long;
}