Given three numbers N, S and X the task is to find if it is possible to construct a sequence A of length N, where each A[i] >= 0 for 1<=i<=N and the sum of all numbers in a sequence is equal to S, and the bit-wise XOR of sequence equals to X.
Examples:
Input: N = 3, S = 10, X = 4
Output: Yes
Explanation: One of the sequence possible is {4, 3, 3} where sum equals 10 and XOR equals 4Input: N = 1, S = 5, X = 3
Output: No
Approach: Lets consider the following test cases.
Case-1: When N equals 1 it can be easily seen that when (S equals X) then only return “Yes” otherwise “No“.
Case-2: When N is greater than equal to 3, use the formula (a + b) = (a xor b) + 2(a and b) Here it can be seen that (a + b) = S and (a xor b) = X so equation becomes S = X + 2(a.b). Therefore, (S-X) should be even because on right side we have 2(a.b). So, it can be said that is S is odd then X is odd and if S is even then X is even then only, (S-X) is also even which can be checked by (S%2 == X%2) also S >= X otherwise A.B turns negative Which is not possible.
Case-3: For the case N equals 3, it is something like A + B + C = S and A^B^C = X. Use the property A^A = 0 and 0^A = A => X + ( S – X)/2 + (S – X)/2 = X + (S-X) => X + ( S – X)/2 + (S – X)/2 = S and also this way: X ^( (S – X)/2 ^ (S-X)/2 ) = X ^ 0 = X. Hence, it is proved that for N == 3 there will always be such sequence and we can just return “Yes“.
Case-4: When N == 2 and (S%2 == X%2) and S >= X, assume A + B == S and (A^B) == X then ( A and B) == (S-X)/2 From the equation discussed above. Let C = A.B. On observing carefully it can be noticed that the bits of C are “1” only when A and B bits are “1” for that position and off otherwise. And X that is xor of A, B has on bit only when there are different bits that is at ith position A has ‘0’ and B has ‘1’ or the just opposite: So looking at this sequence, assign every bits into variable A and B, C = ( S – X)/2. Assign A and B from C -> A = C, B = C
Now add the X into A or B to assign all the ones into A and all zero to B so when we XOR both numbers then the added ‘1’ bits into A will just be opposite to what we added into B that is ‘0’. The fun part is when set bits of C coincides with some set bits of X then it will not give the desired xor of X, Now, A = C + X, B = C. Now A+B = ( C + X) + C = S and when XOR A.B equals X then it can be sure that there exist such pair when A + B == S and (A^B) == X;
Follow the steps below to solve the problem:
- If S is greater than equal to X, and S%2 is equal to X%2 then perform the following steps, else return No.
- If n is greater than equal to 3, then return Yes.
- If n equals 1, and if S equals X, then return Yes else return No.
- If n equals to 2, initialize the variable C as (S-X)/2 and set variables A and B as C and add the value X to the variable A and if A^B equals X, then print Yes else print No.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find if any sequence is// possible or not.string findIfPossible(int N, int S, int X){ if (S >= X and S % 2 == X % 2) { // Since, S is greater than equal to // X, and either both are odd or even // There always exists a sequence if (N >= 3) { return "Yes"; } if (N == 1) { // Only one case possible is // S == X or NOT; if (S == X) { return "Yes"; } else { return "No"; } } // Considering the above conditions true, // check if XOR of S^(S-X) is X or not if (N == 2) { int C = (S - X) / 2; int A = C; int B = C; A = A + X; if (((A ^ B) == X)) { return "Yes"; } else { return "No"; } } } else { return "No"; }}// Driver Codeint main(){ int N = 3, S = 10, X = 4; cout << findIfPossible(N, S, X); return 0;} |
C
// C program for the above approach#include <stdio.h>#include <string.h>#include <stdlib.h>// Function to find if any sequence is// possible or not.char* findIfPossible(int N, int S, int X){ if (S >= X && S % 2 == X % 2) { // Since, S is greater than equal to // X, and either both are odd or even // There always exists a sequence if (N >= 3) { return "Yes"; } if (N == 1) { // Only one case possible is // S == X or NOT; if (S == X) { return "Yes"; } else { return "No"; } } // Considering the above conditions true, // check if XOR of S^(S-X) is X or not if (N == 2) { int C = (S - X) / 2; int A = C; int B = C; A = A + X; if (((A ^ B) == X)) { return "Yes"; } else { return "No"; } } } else { return "No"; }}// Driver Codeint main(){ int N = 3, S = 10, X = 4; printf("%s\n", findIfPossible(N, S, X)); return 0;}// This code is contributed by phalasi. |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find if any sequence is // possible or not. static void findIfPossible(int N, int S, int X) { if ((S >= X) && (S % 2 == X % 2)) { // Since, S is greater than equal to // X, and either both are odd or even // There always exists a sequence if (N >= 3) { System.out.println("Yes"); } if (N == 1) { // Only one case possible is // S == X or NOT; if (S == X) { System.out.println("Yes"); } else { System.out.println("No"); } } // Considering the above conditions true, // check if XOR of S^(S-X) is X or not if (N == 2) { int C = (S - X) / 2; int A = C; int B = C; A = A + X; if (((A ^ B) == X)) { System.out.println("Yes"); } else { System.out.println("No"); } } } else { System.out.println("No"); } } // Driver code public static void main(String args[]) { int N = 3, S = 10, X = 4; findIfPossible(N, S, X); }}// This code is contributed by code_hunt. |
Python3
# Python program for the above approach# Function to find if any sequence is# possible or not.def findIfPossible(N, S, X): if (S >= X and S % 2 == X % 2): # Since, S is greater than equal to # X, and either both are odd or even # There always exists a sequence if (N >= 3): return "Yes" if (N == 1): # Only one case possible is # S == X or NOT if (S == X): return "Yes" else: return "No" # Considering the above conditions true, # check if XOR of S^(S-X) is X or not if (N == 2): C = (S - X) // 2 A = C B = C A = A + X if (((A ^ B) == X)): return "Yes" else: return "No" else: return "No"# Driver CodeN = 3S = 10X = 4print(findIfPossible(N, S, X))# This code is contributed by shivanisinghss2110 |
C#
// C# program for the above approachusing System;public class GFG { // Function to find if any sequence is // possible or not. static void findIfPossible(int N, int S, int X) { if ((S >= X) && (S % 2 == X % 2)) { // Since, S is greater than equal to // X, and either both are odd or even // There always exists a sequence if (N >= 3) { Console.WriteLine("Yes"); } if (N == 1) { // Only one case possible is // S == X or NOT; if (S == X) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } // Considering the above conditions true, // check if XOR of S^(S-X) is X or not if (N == 2) { int C = (S - X) / 2; int A = C; int B = C; A = A + X; if (((A ^ B) == X)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } else { Console.WriteLine("No"); } } // Driver code public static void Main(String[] args) { int N = 3, S = 10, X = 4; findIfPossible(N, S, X); }}// This code is contributed by Princi Singh |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find if any sequence is // possible or not. function findIfPossible(N, S, X) { if (S >= X && S % 2 == X % 2) { // Since, S is greater than equal to // X, and either both are odd or even // There always exists a sequence if (N >= 3) { return "Yes"; } if (N == 1) { // Only one case possible is // S == X or NOT; if (S == X) { return "Yes"; } else { return "No"; } } // Considering the above conditions true, // check if XOR of S^(S-X) is X or not if (N == 2) { let C = (S - X) / 2; let A = C; let B = C; A = A + X; if (((A ^ B) == X)) { return "Yes"; } else { return "No"; } } } else { return "No"; } } // Driver Code let N = 3, S = 10, X = 4; document.write(findIfPossible(N, S, X));// This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!