Sequence of length N with exactly P pairs having XOR equal to X

Updated

Given 3 integers N, P and X, you have to determine if a sequence [S1, S2, …., SN] can be constructed such that any pair of the sequence satisfying the constraint Si XOR Sj = X are exactly P in number.

  • (1 <= i =< j <= N)
  • 1 <= N, P, X <= 2 * 1e4

Example :

Input : N = 4, P = 3 , X = 3
Output : Possible
Explanation :
A possible sequence S = [2,2,1,2] satisfies the given condition, as
there are exactly P = 3 pairs (i,j) such that Si ⊕ Sj = 3 = X.

Input : N = 10, P = 8 , X = 2
Output : Possible
Explanation :
A possible sequence S = [8,12,3,14,8,15,10,10,8,14] satisfies the
given condition, as there are exactly P = 8 pairs with XOR equal to X
= 2.

Input : N = 19, P = 100 , X = 34
Output : Impossible
Explanation :
No such sequence is possible satisfying the constraint

Approach :

  • The first observation is that we do not need to explicitly find the sequence. We just have to say whether such a sequence is possible or not.
  • Note that if any two numbers say A ⊕  B = X, there can be many such pairs (A,B) that give the xor = X. We can simply change appropriate bits and get their xor to be equal to X
  • If we find a suitable sequence of length L < N, then we can easily append some dummy Large Numbers > 2*1e4 in that sequence to make the length to be N while still satisfying all the conditions. This is because the max value of Xor we need is limited by 2* 1e4.
  • SO we will focus on finding the minimum length of the sequence S.

Construction of the sequence :

  • Consider two integers a and b such that a XOR b = X, where frequency of occurrence of a is f1 and that of b is f2. If simply we have f1 * f2 = P, then we can say that we have got a valid sequence.
S = [aaaaaaa........., bbbbbb........] 
      <---f1--------->  <----f2----->

In this sequence S, no of pairs having xor X = f1C1 * f2C1 = f1 * f2 = P. Note, all same pairs a XOR a and b XOR b = 0 and nullified. 

length of this sequence = f1 + f2

SO, we want to minimise(f1 + f2) such that f1 * f2 = P. 
We can use Dynamic Programming to solve this.
  • Since we considered only 1 such pair , there can be many such pairs (a,b) which satisfy the constraint. They might give a lesser value of (f1  + f2). Hence, our sequence can be a concatenation of many such smaller sequences.
  • We can say P is composed of

\[P = \sum (f_i1 * f_i2) \space, \text{and}   \sum(f_i1 + f_i2) <= N\]

We can say dp[i] = min(x + y) where x * y = i
  • After we have precalculated that, we again use DP to find the minimum possible length that can be composed of many sequences.
dp[i] = min(dp[i], dp[j] + dp[i - j]) for each i in 1 to N, for each j in 1 to i

Implementation :

#include <bits/stdc++.h>
using namespace std;
#define int long long int

typedef vector<int> vi;
typedef vector<vector<int> > vvi;

// Function to check if sequence construction is possible
void isSeqPossible(int n, int p, int x)
{
    const int N = 2 * 1e4 + 7;
    vi dp(N, INT_MAX);

    // first dp
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i)
            dp[j] = min(dp[j], i + j / i); // dp[p] = min length of sequence i.e, x + y
                                           // such that (x * y = p)
    }

    // since P is the length, dp[a] = min(dp[a], dp[b] +
    // dp[c]) if b + c = P
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < i; j++)
            dp[i] = min(dp[i], dp[j] + dp[i - j]);
    }

    if (dp[p] <= n)
        cout << "Possible" << endl;
    else
        cout << "Impossible" << endl;
}

// Driver code
signed main()
{

    int n = 10, p = 8, x = 2;
    isSeqPossible(n, p, x);

    return 0;
}
Output

Possible

Time Complexity : O(N * N), for the i-j loop of the DP.

Comment
Next tutorial
Mithlesh Upadhyay Published 20 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials