1

The code is working perfectly for small inputs but there is a runtime error for larger ones. the question was from hackerearth and it went like

You are given a set S consisting of non-negative powers of three S={1, 3, 9, 27} . Consider the sequence of all non-empty subsets of ordered by the value of the sum of their elements. You are also given a single element n. You are required to find the subset at the nth position in the sequence and print it in increasing order of its elements.

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

#define ll long long
ll poww(ll n,ll p)
{
  ll power=1;
  for(ll i=0;i<p;i++)
  {
    power=power*n;
  }
  return power;
}


int main(){
    ll t;
    cin>>t;

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

        ll a[n];
        for(ll i=0; i<n; i++){
            a[i]=poww(3, i);
        }

        ll idx[n]={0};
        ll i=0, count=0; 

        for(ll j=0; j<n; j++){
            if(n & (1<<j)){
                count++;
                idx[i]=a[j];
                i++;
            }
        }

        cout<<count<<endl;
        for(ll k=0; k<i; k++){
            cout<<idx[k]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
James Z
  • 12,209
  • 10
  • 24
  • 44
tanya chhabra
  • 11
  • 2
  • 4
    Variable-length arrays (`ll a[n]`, `ll idx[n]`) are not part of the standard. ([Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097)). I don't know how VLAs are implemented in the different compilers. But my assumption is that it is allocated on the stack in your case, and you encounter a stackoverflow. – t.niese Jul 29 '21 at 08:18
  • 5
    `#define ll long long` is sad, it shows that you value lazyness more than readability – 463035818_is_not_an_ai Jul 29 '21 at 08:19
  • 1
    you should never call `pow(x,i)` (whether its your own implementation or the library one) in a loop with loop counter `i`. Its a waste of cpu, because you recalculate eg `pow(x,2)` `n-1` times, `pow(x,3)` is calculated `n-2` times, etc. – 463035818_is_not_an_ai Jul 29 '21 at 08:22
  • Online compilers will stop the execution of an application after a certain amount otherwise the service would not be useable in a short amount of time. `execution expired` means that your script took too long without finishing. Either run it on your own system. If you get such an error on a coding challenge site, then you need to look for a better algorithm. – t.niese Jul 29 '21 at 08:25
  • @t.niese I'm not sure what it did at all as I forgot to provide input. Maybe, it was waiting for input until time-out... :-) – Scheff's Cat Jul 29 '21 at 08:26
  • @463035818_is_not_a_number then how should i calculate the power if i am not using the pow function ? – tanya chhabra Jul 29 '21 at 08:26
  • That would be quite easy: `a[0] = 1;` and then in a loop `a[i] = a[i - 1] * 3;` – Scheff's Cat Jul 29 '21 at 08:27
  • hint: suppose you are in iteration `k` and you already know the result of `pow(x,k)`, what do you have to do to get `pow(x,k+1)` for the next iteration? – 463035818_is_not_an_ai Jul 29 '21 at 08:27
  • Okay got it thanks a lot – tanya chhabra Jul 29 '21 at 08:28
  • 1
    @tanyachhabra -- Instead of crazy macros like `ll`, use `int64_t`. You now know that the type is a 64-bit integer, and it is just a few more letters than typing `ll`. Thus the excuse of having to type `long long` is now a moot point. – PaulMcKenzie Jul 29 '21 at 09:04

0 Answers0