PALSUM - Editorial

editorial
, ,
21

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!

22

#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

23

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;
}
24

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;
}