[Codefights] Count Sum of Two Representations 2

Problem

Given integers n, l and r, find the number of ways to represent n as a sum of two integers A and B such that l ≤ A ≤ B ≤ r.

Example

For n = 6, l = 2 and r = 4, the output should be
countSumOfTwoRepresentations2(n, l, r) = 2.

There are just two ways to write 6 as A + B, where 2 ≤ A ≤ B ≤ 4: 6 = 2 + 4 and 6 = 3 + 3.


 

Solution

[0, [n/2-l, r-n/2].min + (n+1)%2].max
(i.e. Max( 0 , Min(n/2-l, r-n/2) + (n+1)%2 ) )

Explanation

We can solve this problem with a loop, but there is a “simpler” or “shorter” way.

Without a given range, the number of ways to represent the sum of n can be determined by n/2

n => # ways
2 => 1 … (1, 1)
3 => 1 … (1, 2)
4 => 2 … [(1,3), (2, 2)]
5 => 2 … [(1,4), (2,3)]
6 => 3 … [(1,5), (2,4), (3,4)]

However, we are looking for the number of ways to represent within a range of lower bound, l, and higher bound, r.

If we only had a lower bound, we would have…
(n/2 – l) + (n+1)%2

  • n/2 – l => l ways less than the total # of ways because we used to start at 1, but now we start at l
  • (n+1)%2 => +1 if n is even, +0 if odd
n = 6
l = 2

n/2 - l = 1
(n+1)%2 = 1

# ways = 1 + 1 = 2
Proof: [(2,4),(3,3)]

If we only had a higher bound, we would have…
(r – n/2) + (n+1)%2 with similar explanation as above

Now, we have both the lower and the higher bound.
So we take the minimum between the two. Meaning, we are taking the “stricter” bound.
Min(n/2 – l , r – n/2) + (n+1)%2

Since # of ways cannot be negative, our answer would be
Max(0, Min(n/2 – l , r – n/2) + (n+1)%2)

[Codefights] Equal Pair of Bits

Problem

You’re given two integers, n and m. Find position of the rightmost pair of equal bits in their binary representations (it is guaranteed that such a pair exists), counting from right to left.

Return the value of 2position_of_the_found_pair (0-based).

Example

For n = 10 and m = 11, the output should be
equalPairOfBits(n, m) = 2.

1010 = 10102, 1110 = 10112, the position of the rightmost pair of equal bits is the bit at position 1 (0-based) from the right in the binary representations.
So the answer is 21 = 2.


 

Solution

  • ~(n ^ m) & ((n ^ m) + 1)
  • ~(n ^ m) & -(~(n ^ m))

Explanation

Similar to previous post of “Different Rightmost Bit”, if we do XOR operation between the two numbers, we have 1 in every position that differs.

n = 1010 = 10102
m = 1110 = 10112

n XOR m = 1010^ 1011= 00012

Since 1 bit means the two number differed in that position, the rightmost 0 bit is the rightmost position of equal bits.

Let’s take a complement of this.
~00012 = 11102

Now, the rightmost 1 bit is the rightmost position of equal bits.

There are two options to take now.
With our x = n ^ m,

  • ~x & (x+1): AND operation with its complement and x+1
  • ~x & -(~x): AND operation with its complement and negative complement
    • Example is shown in the previous “Different Rightmost Bit” post

[Codefights] Different Rightmost Bit

Problem

You’re given two integers, n and m. Find position of the rightmost bit in which they differ in their binary representations (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2position_of_the_found_bit (0-based).

Example

  • For n = 11 and m = 13, the output should be
    differentRightmostBit(n, m) = 2.1110 = 10112, 1310 = 11012, the rightmost bit in which they differ is the bit at position 1(0-based) from the right in the binary representations.
    So the answer is 21 = 2.
  • For n = 7 and m = 23, the output should be
    differentRightmostBit(n, m) = 16.710 = 1112, 2310 = 101112, i.e.

    00111
    10111
    

    So the answer is 24 = 16.


 

Solution

(n ^ m) & -(n ^ m)

Explanation

Let’s take n = 11 and m = 13 for example.
1110 = 10112
1310 = 11012

If we do XOR operation with n and m, we have 1 in every position that differs between the two.
1110 XOR 1310 = 10112 ^ 11012 = 01102

Since we have a bit representation of the positions that differ, we need to find the rightmost 1.

There is a trick to this. Given a number, x,
x & -x gives the rightmost 1
x = 6 = 01102
-x = -6 = 10102

x & -x = 0110& 10102 = 00102

So, (n^m) & -(n^m) is our answer.

 

[Codefights] Swap Adjacent Bits

Problem

You’re given an arbitrary 32-bit integer n. Take its binary representation, split bits into it in pairs (bit number 0 and 1, bit number 2 and 3, etc.) and swap bits in each pair. Then return the result as a decimal number.

Example

  • For n = 13, the output should be
    swapAdjacentBits(n) = 14.

    1310 = 11012 ~> {11}{01}2 ~> 11102 = 1410.

  • For n = 74, the output should be
    swapAdjacentBits(n) = 133.

    7410 = 010010102 ~> {01}{00}{10}{10}2 ~> 100001012 = 13310.
    Note the preceding zero written in front of the initial number: since both numbers are 32-bit integers, they have 32 bits in their binary representation. The preceding zeros in other cases don’t matter, so they are omitted. Here, however, it does make a difference.

Input/Output

  • [time limit] 4000ms (rb)
  • [input] integer n

 

Solution

((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)

Explanation

Let’s take n = 13, for example.
1310 = 11012

(11012 & 10102) >> 1 extracts the higher bits and shifts to the lower bit position.

  • 11012 & 10102 = 10002
  • 10002 >> 1 = 01002

(11012 & 01012) << 1 extracts the lower bits and shifts to the higher bit position.

  • 11012 & 01012 = 01012
  • 01012 << 1 = 10102

So, we combine the two, and we get our swapped bits.

  • 01002 | 10102 = 11102

 

[Codefights] Second-Rightmost Zero Bit

Problem

Presented with the integer n, find the 0-based position of the second rightmost zero bit in its binary representation (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2position_of_the_found_bit.

Example

For n = 37, the output should be
secondRightmostZeroBit(n) = 8.

3710 = 1001012. The second rightmost zero bit is at position 3 (0-based) from the right in the binary representation of n.
Thus, the answer is 23 = 8.

Input/Output

  • [time limit] 4000ms (rb)
  • [input] integer n
    Guaranteed constraints:
    4 ≤ n ≤ 230.
  • [output] integer

 

Solution

~(k = n|n+1) & k+1

Explanation

Before we find the second rightmost, we need to be able to find the first.
To do so…

Suppose we have n = 37.
3710 = 1001012
3810 = 1001102

If we use an OR operator between the two numbers, 37 (n) and 38 (n+1), our first rightmost zero is “gone”. Let’s call this k (i.e. k = n|n+1)

3710 OR 3810 = 1001112

Now, the complement of this is ~k = ~1001112 = 0110002
And k+1 = 1010002

In k’s complement, other than our original first rightmost zero bit, all other “zero bits” will be all 1’s.
In k+1, our wanted “second rightmost zero” will have 1.

So if we use an AND operator between ~k and k+1, only the second zero will be 1 and all others will be 0’s.

~k & (k+1) = 0110002 AND 1010002 = 0010002