tredsused70's blog

By tredsused70, history, 2 months ago,

Hi, I was solving this problem a few minutes ago, and the following problem is a subproblem of that one.

Given integer $n$, $n \ge 3$, and array $a$ consisting of $n - 1$ integers, all of them are equal to some value $b$. Later, some integer $c$, such that $c \ne b$ is selected and inserted into the array $a$ at random position. By given $n$ and $a$ find $c$.

This problem itself isn't so difficult, but with a certain restriction I couldn't solve it. The restriction is folowing: you can't use $if$ and ternary operators in any way.

I came up with the solution, that calls $if$ only one time.

my solution

Can you solve this problem with the given restriction?

UPD: In the comments there is one of the solutions, and I've also came up with one.

my final solution

BledDest's solution is shorter, but mine is easier to understand, at least for me, this is just

spoiler

.

• +10

 » 2 months ago, # |   0 Auto comment: topic has been updated by tredsused70 (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 3 →   +1 Sort any three elements, then let $x$ second element. $c=x\oplus\sum_aa\oplus x$
•  » » 2 months ago, # ^ |   0 I think this will find $b$, not $c$
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Thanks for the answer, but I can't really accept it. First, sorting has $if$ in itself, and second, this approach finds b, and not c. After edit it finds c, but still sorting requires $if$.
 » 2 months ago, # |   0 Might be overkill, but zero if/else statements. code#include using namespace std; int main() { int n; cin >> n; vector a(n); for(int i = 0; i < n; i++) cin >> a[i]; map cnt; for(auto x : a) cnt[x]++; vector> aux; for(auto x : cnt) aux.push_back(make_pair(x.second, x.first)); sort(aux.begin(), aux.end()); cout << aux[0].second << endl; } 
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I believe $sort$ has $if$ in it, as well as $map$.
•  » » » 2 months ago, # ^ |   0 I bet using while when it is supposed to be if isn't gonna cut it?
•  » » » » 2 months ago, # ^ |   0 Yeah
 » 2 months ago, # |   +3 Is !! also banned? If not, then this is the solution#include using namespace std; int main() { int n; cin >> n; vector a(n); for(int i = 0; i < n; i++) cin >> a[i]; int full_xor = 0; for(int i = 0; i < n; i++) full_xor ^= a[i]; long long b = 0; for(int i = 0; i < n; i++) { int pair_xor = (a[i] ^ a[(i + 1) % n]); b += a[i] * ((!!pair_xor) ^ 1); } b /= (n - 2); int ans = full_xor * (n % 2) + (full_xor ^ b) * ((n + 1) % 2); cout << ans << endl; } 
•  » » 2 months ago, # ^ |   +16 Simpler version without !!#include using namespace std; int main() { int n; cin >> n; vector a(n); for(int i = 0; i < n; i++) cin >> a[i]; int full_xor = 0; for(int i = 0; i < n; i++) full_xor ^= a[i]; long long b = 0; for(int i = 0; i < n; i++) { int pair_xor = (a[i] ^ a[(i + 1) % n]); b += a[i] * (!pair_xor); } b /= (n - 2); int ans = full_xor * (n % 2) + (full_xor ^ b) * ((n + 1) % 2); cout << ans << endl; } 
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Thank you for your solution, this is what I've searched for.
 » 2 months ago, # |   +8 I'm pretty late but yeah. Spoiler#include using namespace std; int main(){ int n; cin>>n; vector a(n); for(int i=0;i>a[i]; } int sxor=0; for(int i=0;i
•  » » 2 months ago, # ^ |   +8 Thank you, pretty tricky solution.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 Ooops looks like my solution is wrong when $n$ is even and $a_1=c$, for example:41 2 1 1I guess it doesn't matter anymore, but here is corrected version: Spoiler#include using namespace std; int main(){ int n; cin>>n; vector a(n); for(int i=0;i>a[i]; } int sxor=0; for(int i=0;i
 » 2 months ago, # |   +44 Another solution: int main() { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; int b = (a[0] & a[1]) | (a[1] & a[2]) | (a[0] & a[2]); int c = b; for (int i = 0; i < n; i++) c ^= (a[i] ^ b); cout << c << endl; return 0; } 
•  » » 2 months ago, # ^ |   0 Very cool. I like this solution a lot. It is very simple to understand, even for me, and very slick as well.
 » 2 months ago, # |   +12 The problem is you can't really say if something is an if.(flag ? x : y) is equivalent to x * flag + y * !flag, for example. int main() { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; int res = 0; for (int x : a) res ^= x; res ^= ((n & 1) ^ 1) * ((a[0] == a[1]) * a[0] ^ (a[0] == a[2]) * a[0] ^ (a[1] == a[2]) * a[1]); cout << res << endl; return 0; }