Given two integers X and S, the task is to find the minimum length of the sequence of positive integers such that the sum of their elements is S and the bitwise OR(^) of their elements is X. If there does not exist any sequence which satisfies the above conditions, print ?1.
Examples:
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
Approach: The problem can be solved based on the following observation:
Observations:
- 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 ith bit of X is 0, the ith bit of Ai is 0 for all 1 ? i ? N.
- If the ith bit of X is 1, the ith bit of Ai 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 ith bit:
- ith bit of X is 0: There should be no copies of set bits for the ith bit in (S?X).
- ith bit of X is 1: There can be at most (m?1) copies of set bits for the ith 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.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;bool possible(int x, int s, int m){ // domain validation for function if (s < 0 || x < 0 || m < 0) { return false; } for (int i = 30; i >= 0 && s > 0; i--) { if (((x >> i) & 1) == 1) { int temp = s / (1 << i); temp = temp < m ? temp : m; s -= temp * (1 << i); } } return (s == 0);}// Function to find minimum length// of sequenceint minLength(int x, int s){ int foul = s + 1; int left = 0, right = s + 1, m; s = s - x; while (left < right) { m = (left + (right - left) / 2); bool val = possible(x, s, m - 1); if (val) { right = m; } else { left = m + 1; } } int ret = left < foul ? left : -1; return ret;}// Driver codeint main(){ int X = 13; int S = 23; // Function call cout << (minLength(X, S)); return 0;}// This code is contributed by lokeshpotta20. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;public class GFG { public static boolean possible(int x, int s, int m) { // domain validation for function if (s < 0 || x < 0 || m < 0) { return false; } for (int i = 30; i >= 0 && s > 0; i--) { if (((x >> i) & 1) == 1) { int temp = s / (1 << i); temp = temp < m ? temp : m; s -= temp * (1 << i); } } return (s == 0); } // Function to find minimum length // of sequence public static int minLength(int x, int s) { int foul = s + 1; int left = 0, right = s + 1, m; s = s - x; while (left < right) { m = (left + (right - left) / 2); boolean val = possible(x, s, m - 1); if (val) { right = m; } else { left = m + 1; } } int ret = left < foul ? left : -1; return ret; } // Driver code public static void main(String[] args) { int X = 13; int S = 23; // Function call System.out.println(minLength(X, S)); }} |
Python3
# Python3 program for the above approachdef possible(x, s, m): # domain validation for function if (s < 0 or x < 0 or m < 0): return False i = 30 while(i >= 0): if (((x >> i) & 1) == 1): temp = s // (1 << i) temp = temp if (temp < m) else m s -= temp * (1 << i) if s <= 0: break i -= 1 return True if (s == 0) else False# Function to find minimum length# of sequencedef minLength(x, s): foul = s + 1 left = 0 right = s + 1 m = 0 s = s - x while (left < right): m = (left + (right - left) // 2) val = possible(x, s, m - 1) if (val == True): right = m else: left = m + 1 ret = left if (left < foul) else -1 return ret# Driver codeif __name__ == "__main__": X = 13 S = 23 # Function call print(minLength(X, S))# This code is contributed by Rohit Pradhan. |
C#
// C# program to implement// the above approachusing System;class GFG{ public static bool possible(int x, int s, int m) { // domain validation for function if (s < 0 || x < 0 || m < 0) { return false; } for (int i = 30; i >= 0 && s > 0; i--) { if (((x >> i) & 1) == 1) { int temp = s / (1 << i); temp = temp < m ? temp : m; s -= temp * (1 << i); } } return (s == 0); } // Function to find minimum length // of sequence public static int minLength(int x, int s) { int foul = s + 1; int left = 0, right = s + 1, m; s = s - x; while (left < right) { m = (left + (right - left) / 2); bool val = possible(x, s, m - 1); if (val) { right = m; } else { left = m + 1; } } int ret = left < foul ? left : -1; return ret; }// Driver Codepublic static void Main(){ int X = 13; int S = 23; // Function call Console.Write(minLength(X, S));}}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code to implement the above approach. function possible(x, s, m) { // domain validation for function if (s < 0 || x < 0 || m < 0) { return false; } for (let i = 30; i >= 0 && s > 0; i--) { if (((x >> i) & 1) == 1) { let temp = Math.floor(s / (1 << i)); temp = temp < m ? temp : m; s -= temp * (1 << i); } } return (s == 0); } // Function to find minimum length // of sequence function minLength(x, s) { let foul = s + 1; let left = 0, right = s + 1, m; s = s - x; while (left < right) { m = (left + Math.floor((right - left) / 2)); let val = possible(x, s, m - 1); if (val) { right = m; } else { left = m + 1; } } let ret = left < foul ? left : -1; return ret; } // Drivers code let X = 13; let S = 23; // Function call document.write(minLength(X, S));// This code is contributed by code_hunt.</script> |
Output
3
Time Complexity: O(logS * logX) = O(log (S+X))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments