→ Furina: 大師 11/09 12:17
→ dont: 大師 11/09 19:35
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;
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.243 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731123707.A.194.html