Increasing Sequence with Fixed OR
Problem Statement
You are given a positive integer 𝑛. Find the longest sequence of positive integers 𝑎=[𝑎1,𝑎2,…,𝑎𝑘] that satisfies the following conditions, and print the sequence:
𝑎𝑖≤𝑛 for all 1≤𝑖≤𝑘.
𝑎 is strictly increasing. That is, 𝑎𝑖>𝑎𝑖−1 for all 2≤𝑖≤𝑘.
𝑎𝑖|𝑎𝑖−1=𝑛 for all 2≤𝑖≤𝑘, where | denotes the bitwise OR operation.
Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤1000). Description of the test cases follows.
The only line of each test case contains one integer 𝑛 (1≤𝑛≤1018).
It's guaranteed that the sum of lengths of the longest valid sequences does not exceed 5⋅105.
Output
For each testcase, print two lines. In the first line, print the length of your constructed sequence, 𝑘. In the second line, print 𝑘 positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them.
ExampleinputCopy
outputCopy
Intuition
Links
https://codeforces.com/contest/1988/problem/C
Video Links
https://www.youtube.com/watch?v=sAUI0T6r9TA&t=1161s&ab_channel=CompetitiveProgrammingwithShayan
Approach 1:
Approach 2:
Approach 3:
Approach 4:
Similar Problems
Last updated