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;
}