Palindromic Binary Numbers solution codechef

Palindromic Binary Numbers solution codechef

 

We call a non-negative number xx good if its binary representation is palindromic. For example, 107107 is good because its binary representation is 11010111101011 which is palindromic while 1010 is not good because its binary representation is 10101010 which is not palindromic.

Recall that, a string is said to be palindromic if it reads the same backward as forward.

You are given a number nn. You have to express nn as a sum of at most 1212 good numbers. If there exist multiple answers, print any one of them.

CodeChef Starters 18 Division 3 (Rated) - CodeChef

Palindromic Binary Numbers solution codechef Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each testcase contains a single integer nn.

Output Format

For each testcase, print a single integer mm (1m121≤m≤12), denoting the number of good numbers. In the next line, print a sequence of mm good numbers whose sum is equal to nn. If there are multiple such sequences, print any of them.

Constraints Palindromic Binary Numbers solution codechef

  • 1T10001≤T≤1000
  • 1n10001≤n≤1000

Sample Input 1 

2
24
4

Sample Output 1 

2
21 3
4
1 1 1 1

Explanation Palindromic Binary Numbers solution codechef

Test case 11:

  • 2121 is good because 21=(10101)221=(10101)2 which is palindromic.
  • 33 is good because 3=(11)23=(11)2 which is palindromic.

Test case 22:

  • 11 is good because 1=(1)21=(1)2 which is palindromic.

Here ()2()2 denotes binary representation of the number.

Leave a Comment