tredsused70's blog

An unexpectedly difficult problem
By tredsused70, history, 22 months ago, In English

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

.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tredsused70 (previous revision, new revision, compare).

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Sort any three elements, then let $$$x$$$ second element. $$$c=x\oplus\sum_aa\oplus x$$$

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this will find $$$b$$$, not $$$c$$$

    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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$$$.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Might be overkill, but zero if/else statements.

code
→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Is !! also banned?

If not, then this is the solution
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it
    Simpler version without `!!`
    → Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm pretty late but yeah.

Spoiler
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you, pretty tricky solution.

    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Ooops looks like my solution is wrong when $$$n$$$ is even and $$$a_1=c$$$, for example:

    4

    1 2 1 1

    I guess it doesn't matter anymore, but here is corrected version:

    Spoiler
    → Reply
»
22 months ago, # |
  Vote: I like it +44 Vote: I do not like it

Another solution:

int main() {
    int n;
    cin >> n;
    vector<int> 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;
}
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very cool. I like this solution a lot. It is very simple to understand, even for me, and very slick as well.

    → Reply
»
22 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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<int> 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;
}
→ Reply