partition problem in O(n^2) and O(n) space

partition problem

#include <iostream>
#include<cstring>
using namespace std;

int main() {
    int test ;
    cin>> test ;
    while (test > 0 )
    {
        int no_items ;
        cin>>no_items;
        int W[no_items];
        int sum =0 ;
        for (int i = 0 ; i<no_items ; i++ )
        {
            cin>>W[i];
            sum = sum + W[i];
        }
        if (sum%2 !=0)
        {
            cout <<"NO"<<"\n";
            test--;
            continue  ;
        }
       
        int A[sum/2];
        memset(A,0,sizeof(A));
        A[0]=1;
        for (int j= sum/2; j>0; j--)
        {
            if (A[j]==W[0])
            {
                A[j] = 1 ;
            }
        }
        for (int i = 1 ; i< no_items ; i++)
        {
            for (int j= sum/2 ; j>0 ; j--)
            {
                     if(A[j]!=1)
                     {
                         if ( (j>=W[i]) && (A[j-W[i]]==1))
                         A[j]=1;
                     }
            }
        }
        if (A[sum/2]==1)
        cout <<"YES"<<"\n";
        else
        cout <<"NO"<<"\n";
        test -- ;
    }
    return 0;
}


2
4
1 5 11 5
3
1 3 5

Cipher both approaches O(n) and O(n^2)

Jack and Daniel are friends.
They want to encrypt their conversation so that they can save themselves from interception by a detective agency. So they invent a new cipher.
Every message is encoded to its binary representation of length .
Then it is written down times, shifted by bits.
If and it looks so:

1001010   
 1001010  
  1001010 
   1001010

Then calculate XOR in every column and write it down. This number is called . For example, XOR-ing the numbers in the above example results in

1110100110

Then the encoded message and are sent to Daniel.
Jack is using this encoding algorithm and asks Daniel to implement a decoding algorithm.
Can you help Daniel implement this?
Input Format
The first line contains two integers and .
The second line contains string of length consisting of ones and zeros.
Output Format
Decoded message of length , consisting of ones and zeros.
Constraints



It is guaranteed that is correct.
Sample Input#00

7 4
1110100110

Sample Output#00

1001010

Sample Input#01

6 2
1110001

Sample Output#01

101111

Explanation
Input#00

1001010
 1001010
  1001010
   1001010
----------
1110100110

Input#01

101111
 101111
-------
1110001

this is O(n²) approach

)

#include <stdio.h>

#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int  n , k ;
    scanf("%d %d",&n,&k);
   
    char a[n+k];
    scanf("%s",a);
    a[n]='\0';
    char final[n+1];

    final[0]= a[0];
    final[n]= a[n];
  
    printf("%c",final[0]);
    for (int i = 1;i<n;i++)
    {
        final[i]='0';
        int answer = 0;
        for (int m = i-1;((m>=0)&&(m>=(i-k+1)));m--)       
        {answer = (final[m]-'0') ^ answer  ;
        }
        final[i] = ( (a[i]-'0') ^ answer ) +'0';
        final[i]
        printf("%c",final[i]);
    }
   
    return 0;
}

approach (2)  this is O(N) 

 #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int  n , k ;
    scanf("%d %d",&n,&k);
   
    char a[n+k];
    scanf("%s",a);
    a[n]='\0';
    char final[n+1];

    final[0]= a[0];
    final[n]= a[n];
  
    printf("%c",final[0]);
    int answer = 0;
    for (int i = 1;i<n;i++)
    {
        final[i]='0';       
       answer = (final[i-1]-'0') ^ answer  ;
        if (i>=k)
        {
            answer = answer ^(final[i-k]-'0');
        }
        final[i] = ( (a[i]-'0') ^ answer ) +'0';
        printf("%c",final[i]);
    }
   
    return 0;
}

Xor-sequence (a very good question on 1 to n ........in constant time O(1) approach

An array, , is defined as follows:

• 
  
• for , where is the symbol for XOR

You must answer questions. Each question, is in the form , and the answer is (the Xor-Sum of segment ).
Print the answer to each question.

Input Format

The first line contains (the number of questions).
The subsequent lines each contain two space separated integers, and , respectively. Line contains and .
Constraints


Subtasks
For score:

Output Format

On a new line for each test case , print the exclusive-or of 's elements in the inclusive range between indices and .

Sample Input

3
2 4
2 8
5 9

Sample Output

7
9
15

Explanation

The beginning of our array looks like this:
Test Case 0:

Test Case 1:

Test Case 2:


#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
long actual_number(long m)
{
    if (m%4==0)
        return m;
    if (m%4==1)
        return 1;
    if ((m%4)==2)
        return m+1;
    if (m%4==3)
        return 0;
    return 0;
}
int main(){
    int Q;
    scanf("%d",&Q);
    for(int a0 = 0; a0 < Q; a0++){
        long L;
        long R;
        scanf("%ld %ld",&L,&R);
        long final=0 ;
        long final1=0 ,final2=0;
       while (L%4!=0 && L<R)
        { final1= (final1 ^ actual_number (L)) ;
          // printf("%d  ",actual_number);
            L++;
        }
        if (L==R )
        {
            printf("%ld\n",final1^actual_number(L));
            continue;
        }
           while (R%4!=3 && L<R)
        {
            final2 = (final2^actual_number(R));
            //  printf("%d   ",actual_number(R));
            R--;
        }
        if (L==R)
        {
            printf("%ld\n",(final2^final1^actual_number(R)));
            continue;
        }
       // printf("\nL is %ld and R is %ld",L,R);
       // printf("\n final1 is %d and final 2 is %d",final1,final2);
        if (((R-L+1)%8)==0  )
        {
            final = final1^final2;
        }
        else          // it will definetlty be 3
        {
            final = (final1 ^ final2 ^ 2);
          
        }
       
         printf("%ld\n",final);
    }
   
    return 0;
}