Минимальное количество элементов, имеющих сумму S и побитовое ИЛИ как X

Даны два целых числа X и S , задача состоит в том, чтобы найти минимальную длину последовательности положительных целых чисел, такую, что сумма их элементов равна S , а побитовое ИЛИ(^) их элементов равно X . Если не существует ни одной последовательности, удовлетворяющей вышеуказанным условиям, выведите −1.

Примеры:

Input: X = 13, S = 23
Output: 3

Explanation: One of the valid sequence of length 3 is [9, 9, 5] 
such that 9+9+5 =23 and 9^9^5 = 13. 
Another valid sequence is {13, 9, 1}
It can be shown that there is no valid array with length < 3 .

Input: X = 6, S = 13
Output: -1

Подход: Задача может быть решена на основе следующего наблюдения:

Наблюдения:

• X is one of the elements of the sequence: Considering the binary representation of X, we want to find a sequence of integers A of length N such that:
  • If the i^th bit of X is 0, the i^th bit of A_i is 0 for all 1 ≤ i ≤ N. 
  • If the ith bit of X is 1, the i^th bit of A_i is 1 for at least one 1 ≤ i ≤ N.
  • We know that the sum of elements S ≥ X. To fulfill the second condition, we can simply have X as one of the elements of the sequence.
• Binary Search over the length of sequence: Suppose that a length N satisfies the given conditions:
  • We can simply add a 0 to the previous sequence of length N. Thus, length (N+1) would also satisfy all conditions.
  • We cannot say for sure if we can generate a sequence of length (N−1) satisfying all conditions based on the given result of length N. Thus, we would have to check again.                                                                                              
  • We can apply binary search on the length of the sequence. If the current length m satisfies all conditions, we look for a smaller value of length, else, we look for a greater value of length.                                                                          
  • If no possible m exists between lower and upper bound, the answer is −1.
• Check function of binary search: We need to determine if a sequence of length m can have sum of elements equal to S and bitwise or of elements equal to X.                                                                                                                                                                  
  • If we are given a length m, each (set) bit can have m copies. Since one of the elements is X, we have m−1 copies left for each set bit.                                                                                                                                                                                                                   
  • Our problem reduces to finding a sequence of length (m−1) with sum (S−X) and bitwise or equal to (Y?X=X)                                  
  • We traverse the bits of X from highest bit to lowest bit (not including the lowest bit). Consider the i^th bit:
    • i^th bit of X is 0: There should be no copies of set bits for the i^th bit in (S−X). 
    • i^th bit of X is 1: There can be at most (m−1) copies of set bits for the i^th bit in (S−X). All excess copies can be transferred to the (i+1)^th bit of (S−X) (by multiplying with a factor of 2).
• For the lowest bit:                                                                                                                                                                                        
  • Lowest bit of X is 0: If there are any copies of set bits for the lowest bit in (S−X), sequence of length m does not exist, else it exists.
  • Lowest bit of X is 1: If the number of copies of set bits for the lowest bit in (S−X) exceeds (m−1), sequence of length m does not exist, else it exists.

Ниже приведена реализация вышеуказанного подхода:

Выход

3

Временная сложность: O(logS * logX) = O(log(S+X))
Вспомогательное пространство: O(1)