Subarray XOR Solution Codechef

by

Subarray XOR Solution Codechef

Mary loves binary strings. Given a binary string S, she defines the beauty of the string as the bitwise XOR of decimal representations of all substrings of S.

Find the beauty of string S. Since the answer can be huge, print it modulo 998244353.

For example, the decimal representation of binary string 1101 is 1⋅23+1⋅22+0⋅21+1⋅20=8+4+0+1=13. Kindly refer sample explanation for more such examples.

A string A is a substring of a string B if A can be obtained from B by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.

Input Format

  • The first line of input contains a single integer T, denoting the number of test cases. The description of test cases follow.
  • First line of each test case contains one integer N – the length of the binary string.
  • Second line of each test case contains the binary string S.

Output Format

For each test case, output in a single line, beauty of the string modulo 998244353.

Constraints

  • 1≤T≤100
  • 1≤N≤105
  • Sum of N over all test cases does not exceed 2⋅105

Sample Input 1

3
2
10
3
101
4
1111

Sample Output 1

3
6
12

Explanation

  • Test Case 1: All substrings of the string S=10 are [1,0,10]. The decimal representation of these substrings is denoted by the array [1,0,2]. Bitwise XOR of all these values is 1⊕0⊕2=3.
  • Test Case 2: All substrings of the string S=101 are [1,0,1,10,01,101]. The decimal representation of these substrings is denoted by the array [1,0,1,2,1,5]. Bitwise XOR of all these values is: 1⊕0⊕1⊕2⊕1⊕5=6.
  • Test Case 3: All substrings of the string S=1111 are [1,1,1,1,11,11,11,111,111,1111]. The decimal representation of these substrings is denoted by the array [1,1,1,1,3,3,3,7,7,15]. Bitwise XOR of all these values is: 1⊕1⊕1⊕1⊕3⊕3⊕3⊕7⊕7⊕15=12.

SOLUTION

Program: Subarray XOR Solution Codechef in Python

mod=998244353
for i in range(int(input())):
    n=int(input())
    l=list(map(int,input()))
    temp=[0 for i in range(n)]
    ans=[0 for i in range(n)]
    for i in range(n):
        if l[i]==0 or i%2==1:
            continue
        temp[i]+=1
    ans[0]=temp[0]
    for i in range(1,n):
        ans[i]=(temp[i]+ans[i-1])%2
    mul=1
    out=0
    for i in range(n-1,-1,-1):
        if ans[i]==0:
            mul*=2
            mul%=mod
            continue
        out+=mul
        out%=mod
        mul*=2
        mul%=mod
    print(out)

Program: Subarray XOR Solution Codechef in C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long n;
        cin>>n;
        string s;
        cin>>s;
        long long result[n]={0};
        if(s[0]=='1')
        {
            result[0]=1;
        }
        long long prev=result[0];
        for(int i=1;i<n;i++)
        {
            if(s[i]=='1')
            {
                prev+=(i+1);
            }
            result[i]=prev;
            result[i]=result[i]%2;
        }
        long long ans=0,power=1;
        for(int i=n-1;i>=0;i--)
        {
            if(result[i])
            {
                ans+=power;
                ans%=998244353;
            }
            power*=2;
            power%=998244353;
        }
        cout<<ans%998244353<<endl;
    }
}

Program: Subarray XOR Solution Codechef in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(rd.readLine());
        int mod = 998244353;
        while(t--!=0){
            int n = Integer.parseInt(rd.readLine());
            StringBuilder s = new StringBuilder(rd.readLine());
            
            long[] arr = new long[n];
                
            arr[0] = (s.charAt(0)=='1') ? 1 : 0;
            int noOf1s = (int)arr[0];    
            
            if(arr[0]==1){
                s.setCharAt(0, '1');
            }
            else s.setCharAt(0, '0');
            
            for (int i = 1; i < n; i++){
                if(s.charAt(i)=='1') noOf1s++;
                
                arr[i] = arr[i-1] + noOf1s;
                
                long temp = (i+1)*(arr[i]-arr[i-1]) - arr[i-1];
                if(temp%2==1){
                    s.setCharAt(i, '1');
                }
                else{
                    s.setCharAt(i, '0');
                }
            }             
            int pwrTwo[] = new int[n];
            pwrTwo[0] = 1;
            
            for (int i = 1; i < n; i++){
                pwrTwo[i] = (pwrTwo[i-1]*2)%mod;
            } 
            int res = 0;
            int i = 0;
            int j = n-1;
            
            while(i < n){
                if(s.charAt(j)=='1'){
                    res+=(pwrTwo[i]);
                    res%=mod;
                }
                i++;
                j--;
            }
            System.out.println(res);
        }
	}
}

Codechef March Long Challenge 2022 Solutions

Leave a Comment

eight − one =