But we can write 2 as both 10 and 010, tell me if we 010 doesn’t mean 2? same for every pow of 2.
Leading zeroes are ignored unless explicitly mentioned.
Okay. Thanks for replying.
as you are saying this ae the list 1,3,5,9,17,33,65,129,257,513
my question is 7,15,… also gives palindromic as 7’s binary is 111 and 15’s is 1111
can someone explain why they are only considering above list ??
1 Like
same question
We are not required to provide the optimal solution to solve this problem. For example, a large palindromic number, such as 765 (or 1011111101 in binary format), can be just represented by itself. But the solution from the editorial will decompose it into a sum of multiple numbers. And this is perfectly fine, because it does not exceed the 12 numbers limit.
I know that any number n >= 1 can be expressed as a sum of power of 2.
But here how can we know that n can be expressed as sum of no’s whose binary string format is palindrome ?
7 and 15 aren’t of the format 10…01. If you observe he did a +1 to 0,2,4,8…,512 to get 1,3,5,9…513 which would result in every number being a palindrome
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;cin>>n;
vector<int> ans;
int bits = (int)log2(n)+1;
for(int i=bits-1;n>0 and i>=0;--i){
int t = (1<<i);
if(t>1) t--;
if(n-t>=0){
ans.push_back(t);
n-=t;
}
}
while(n) {ans.push_back(1);n--;}
cout<<ans.size()<<endl;
for(auto i:ans) cout<<i<<" ";
cout<<endl;
}
int main()
{
int t;cin>>t;
while(t--) solve();
return 0;
}
could you provide edge cases for this approach?
Here is my code based on ssvb’s idea and submission
/* Use the observation that 2^x - 1 and 2^x + 1 are
* palindrome.
* For example, 2 = (10), 3 = (11) 1 = 1
* 8 = (1000), 9 = 1001, 7 = 111
* We do not include leading zeroes.
*
*
* Then, since we know N = 1000 < 2^10,
* iterate from 1...10
* and check (1 << i) & n.
* If (1 << i) & n is true, then
* add (1 << i) to a vector.
*/
void palindromic_binary_sum() {
int n;
cin >> n;
vector<int> good_numbers;
// Variable used to add close to even amounts of 2^x + 1 and 2^x - 1
int parity = 0;
// O(1)
for (int i = 1; i < 10; i++) {
int bitmask = (1 << i);
if ((bitmask & n)) {
if (parity) {
good_numbers.push_back(bitmask + 1);
} else {
good_numbers.push_back(bitmask - 1);
}
parity ^= 1;
}
}
/* The number of good numbers is proportional to log N, as
* n can have at most log(N) bits set to 1.
* Therefore, O(log_N + a), where a is the number of 1's that we add.
*/
int sum_so_far = accumulate(begin(good_numbers), end(good_numbers), 0);
/* Since the sum of the good numbers is not guaranteed to be equal to n,
* for example,
* if n = 2, the only good number is 1, so sum_so_far = 1
* if n = 5, the only good number is 3, so sum_so_far = 3.
* , so print n - sum_so_far amount of 1's.
* Time complexity: O(a) where a is the number of 1's that we have to add.
*/
while (sum_so_far < n) {
good_numbers.push_back(1);
sum_so_far++;
}
//Print answer
cout << good_numbers.size() << endl;
// O(log N)
for_each(cbegin(good_numbers), cend(good_numbers), [](int good_number) {
cout << good_number << " ";
});
cout << endl;
// Total time complexity per test case: O(log N)
// The number of 1's that are being added is trival as N gets bigger.
}
we consider only the numbers, whose binary representation are of the form 100…001
does the palindromes in 10…01 form only counts to good numbers ?
what about these :- {7,15,21,27,31,45,63,…}
?
does 7 , 15 ,… are not palindrome ?
21,27 ,45 is palindrome , rit ? and it doesnt come to 2^x - 1 or 2^x + 1
21,27 ,45 is palindrome , rit ? and it doesnt come to 2^x - 1 or 2^x + 1
Everyone knows that 21 (which is 10101 in binary format) can be represented as 2^0 + 2^2 + 2^4. Now in order to turn it into a sum of palindromes, this expression can be changed to (2^0 - 1) + (2^2 + 1) + (2^4 - 1). This became a sum of 3 palindromic numbers. Except that there’s one minor problem: -1 is used twice, +1 is used once and they don’t compensate each other. But this may only happen when we have an odd amount of numbers in the answer. And can be easily resolved by just appending 1 to the answer: (2^0 - 1) + (2^2 + 1) + (2^4 - 1) + 1
BTW, this particular solution may output a useless 0 as a part of the sum (if bit 0 is set). But this is fine, because the judge system happens to consider 0 as a valid palindrome too (if this wasn’t the case, then 0 could be filtered out). Here’s a link to my C++ submission in practice mode: CodeChef: Practical coding for everyone
It’s also easy to prove that this solution never produces a sum of more than 10 numbers in the answer, so the problem’s constraints are very generous.
Just rate my approach.Solution is being accepted.
I just used the logic to use the numbers which are 1 less than the numbers which can be expressed as the power of 2 ,for example 0,1,11,111,1111 etc. I stored all such numbers (less than 1000) inside a vector v1. Jumping to the approach I searched a number less than equal to the ‘n’ in the vector v1 using upper bound approach.and subtracted it from n .Continuing this process till n!=0 .
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int main ()
{
int i=0,t,k;
vector <int>v1;
while(1)
{
if((1<<i)>1000)
break;
v1.push_back(1<<i);
v1[i]=v1[i]-1;
i++;
}
k=v1.size();
cin>>t;
while (t--)
{
int n,i,nearest,count=0;
vector<int> v2;
cin>>n;
while(n!=0)
{
auto j=upper_bound(v1.begin(),v1.end(),n);
j--;
n=n-*j;
v2.push_back(*j);
count++;
}
cout<<count<<"\n";
for(i=0;i<count;i++)
cout<<v2[i]<<" ";
cout<<"\n";
}
return 0;
}
easy to understand>>
#include<bits/stdc++.h>
using namespace std;
string decimalToBinary(int n)
{
string s = bitset<32> (n).to_string();
const auto loc1 = s.find('1');
if(loc1 != string::npos)
return s.substr(loc1);
return "0";
}
bool isPalindrome(string str)//for strings only
{
int l = 0;
int h =str.size() - 1;
while (h > l)
{
if (str[l++] != str[h--])
{
return false;
}
}
return true;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<int>pal;
for (int i = 1; i <=1000 ; ++i)
{
if(isPalindrome(decimalToBinary(i)))pal.push_back(i);
}
reverse(pal.begin(),pal.end());
int t;
cin >> t;
while(t--){
int n,i=0;
cin >> n;
vector<int>ans;
while(n && pal.size()>i){
if(pal[i]<=n){
ans.push_back(pal[i]);
n-=pal[i];
}
else i++;
}
cout << ans.size() <<"\n";
for(int i=0;i<ans.size();i++)cout << ans[i] <<" ";
cout << "\n";
}
}
1 Like
Can you help me to find what’s wrong in this program. My approach was 2^m(where m-[0,9]), In binary representation (1,11,101,1001,10001,100001…). These are palindrome and reducing these palindrome numbers to the original number(n) until n becomes 0.
import math
T=int(input())
for t in range(T):
n=int(input())
if(n<=0):
print(0)
print(0)
break
index=0
ans=[]
while(n>0):
for i in range(11):
if(2**i+1>=n):
index=i-1
break
ans.append(math.floor(2**index)+1)
n=n-((2**index)+1)
print(len(ans))
for i in range(len(ans)):
print(ans[i],end=' ')
print()
Thank You!
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T → 0){
int N;
int array[12] = {0};
cin >> N;
int total = N;
int result = 0;
int i = 0;
while(total>1){
result = log2(total);
int num = pow(2,result)-1;
array[i] = num;
total = total - num;
i++;
}
if(total==1)
array[i] = 1;
for(int j=0;j<=i && array[j] != 0;j++){
cout << array[j];
if(j<=i-1){
cout << " ";
}
}
cout << endl;
}
}
where am I incorrect…?
I used the logic 2^n - 1 is always palindromic
my approach
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int powerOfTwo(int n)
{
return n && (!(n & (n-1)));
}
int highestPowerof2(int n)
{
int res = 0;
for (int i=n; i>=1; i--)
{
if ((i & (i-1)) == 0)
{
res = i;
break;
}
}
return res;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vi elements;
while(n>=1)
{
if(n>1)
{
int ele = highestPowerof2(n);
if(powerOfTwo(ele))
{
n = n-(ele-1);elements.pb(ele-1);
}
}
else
{
elements.pb(1);
n = 0;
}
}
cout<<elements.size()<<"\n";
for (auto i : elements) {
cout<<i<<" ";
}
cout<<"\n";
}
return 0;
}
Greedy solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
const int MX = 1000;
vector<int> good; // stores all good numbers in [1, 1000]
for (int i = 1; i <= MX; i++) {
bool ok = 1; // check if 'i' is palindrome
for (int len = 32 - __builtin_clz(i), j = 0; j < len / 2; j++) {
ok &= (i >> j & 1) == (i >> (len - j - 1) & 1);
}
if (ok) good.push_back(i);
}
int tc;
for (cin >> tc; tc; tc--) {
int n, now = 0;
cin >> n;
vector<int> ans;
while (now < n) {
int dif = n - now;
auto it = upper_bound(good.begin(), good.end(), dif);
it--;
now += *it;
ans.push_back(*it);
}
assert((int) ans.size() <= 12);
assert(now == n);
cout << ans.size() << '\n';
for (int i = 0; i < (int) ans.size(); i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
return 0;
}