twoseven's blog

Need help in these Problems
By twoseven, history, 3 years ago, In English
Problem 1
Problem 2

It would be very helpful if some can share their approach to these problems. Thanks!!

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please share problem links ?

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

    These problems were asked in the coding round of a company some time ago. I don't have any links to these problems.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem 1: may be it will help

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

The first problem seems easy:

First, notice that any even whole number up to 4 * 1e18 can be expressed as the sum of two prime numbers (experimentally proven), except 2. Second , notice, that in order for their XOR to be even, they should have the same last bit in their binary represntation.

After that we notice, that all numbers except 2 and 4 that are even are expressed as sum of two odd primes, as such it means that they both have 1 in their binary representation as the last bit, which means that their XOR is even.

As such, our problem is reduced to finding pairs of indexes i, j such that a[i] * a[j] is even and not equal to either 2 or 4. After that, the problem seems easy.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks, I got it !!

    But why it's wrong for 4 ? We can break 4 as 2 + 2 and 2 ^ 2 is even.

    → Reply