Increasing Sequence with Fixed OR

Problem Statement

You are given a positive integer $n$𝑛. Find the longest sequence of positive integers $a=[a1,a2,…,ak]$𝑎=[𝑎1,𝑎2,…,𝑎𝑘] that satisfies the following conditions, and print the sequence:

• $ai≤n$𝑎𝑖≤𝑛 for all $1≤i≤k$1≤𝑖≤𝑘.

• $a$𝑎 is strictly increasing. That is, $ai>ai−1$𝑎𝑖>𝑎𝑖−1 for all $2≤i≤k$2≤𝑖≤𝑘.

• $ai|ai−1=n$𝑎𝑖|𝑎𝑖−1=𝑛 for all $2≤i≤k$2≤𝑖≤𝑘, where $|$| denotes the bitwise OR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$𝑡 ($1≤t≤1000$1≤𝑡≤1000). Description of the test cases follows.

The only line of each test case contains one integer $n$𝑛 ($1≤n≤1018$1≤𝑛≤1018).

It's guaranteed that the sum of lengths of the longest valid sequences does not exceed $5⋅105$5⋅105.

Output

For each testcase, print two lines. In the first line, print the length of your constructed sequence, $k$𝑘. In the second line, print $k$𝑘 positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them.

ExampleinputCopy

4131423

outputCopy

1
1
3
1 2 3
4
4 10 12 14
5
7 18 21 22 23

Intuition

Check Initially

If

    // 23
    // 10111

    // 00101 5
    // 10010 18
    // 10101 21
    // 10110 22
    // 10111 23

If in 5 we put 1 initially, then we will have to put one in 18 also
Due to sum condition

So like that we generate the nums,

We get a alternating pattern 

Code is difficult refer it

Links

https://codeforces.com/contest/1988/problem/C

Video Links

https://www.youtube.com/watch?v=sAUI0T6r9TA&t=1161s&ab_channel=CompetitiveProgrammingwithShayan

Approach 1:

C++

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

int main(){

    int t;
    while(t--){
        int n;
        cin>>n;

        if(__builtin_popcountll(n) == 1){
            cout<<"1\n"<<n<<endl;
            continue;
        }

        int res = __builtin_popcountll(n) + 1;
        cout<<res<<endl;

    // 23
    // 10111

    // 00101 5
    // 10010 18
    // 10101 21
    // 10110 22
    // 10111 23
        for(int i=0; i<res; i++){
            int cnt = 0, cur = 0;
            int val = 0;

            for(int l = 64; l>=0; l--){
                if(n & (1ll<<l)){
                    cnt ++;
                    /*
                    Basically, Only i ones will get printed, 
                    When i = 0
                    Initial ones not printed, 
                    When i = 1, only initial one printed, then alternating because of curr
                    For zero we just ignore
                    Only at one we do alternating

                    Refer Explanation for more
                    */ 
                    
                    if(cnt <= i)
                        val += (1ll<<l);
                    else{
                        if(cur)
                            val += (1ll<<l);
                        cur = 1-cur;
                    }
                }
            }

            cout<<val<<" ";
        }  

        cout<<endl;
    }
}

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems