2
\$\begingroup\$

here is the problem statement

You are given an array a of length n consisting of non-negative integers.

You have to calculate the value of \$\sum_{l=1}^n \sum_{r=l}^n f(l,r)\cdot (r - l + 1)\$ where \$f(l, r)\$ is \$a_l \oplus a_{l+1} \oplus ... \oplus a_{r-1} \oplus a_r\$ (the character \$\oplus\$ denotes bitwise XOR)

Since the answer can be very large, print it modulo \$998244353\$.

Input

The first line contains an integer n (\$1 \le n \le 3\cdot 10^5\$ - the length of the array a).

The second line contains n integers \$a_1, a_2, ... a_n (0 \le a_i \le 10^9)\$

Output

Print one integer - the value of \$\sum_{l=1}^n \sum_{r=l}^n f(l,r)\cdot (r - l + 1)\$ taken modulo \$998244353\$.

Examples
input
3
1 3 2
output
12

input
4
39 68 31 80
output
1337

input
7
313539461 779847196 221612534 488613315 633203958 394620685 761188160
output
257421502

Here is my code, it works but is slow for the given values in the problem. (I know only C, a beginner at that).
Could you provide faster code?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long int f(long long int *a,long long int b, long long int c);
long long int sum(long long int arraysize, long long int*a);

long long int main ()
{
    clock_t start, end;
    double cpu_time_used;
    long long int n, ans;
    scanf("%lld", &n);

    long long int *a = (long long int *)malloc(n*sizeof(long long int));
    for (long long int i = 0 ; i < n ; i++)
    {
        scanf("%lld", a+i);
    }
    start = clock();
    ans = sum(n , a)%998244353;
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("%lld", ans);
    free(a);
    printf("\nf() took %f seconds to execute \n", cpu_time_used);
}

long long int f(long long int *a,long long int n1, long long int n2)
{
    long long int c = a[n1];
    for (long long int i = n1+1; i <=n2; i++)
    {
        c = c ^ a[i];
    }
    return c;
}

long long int sum(long long int arraysize , long long int *a)
{
    long long int value= 0;
    for (long long int i = 0 ; i < arraysize; i++)
    {
        for (long long int j = i, count = 1 ; j < arraysize ; j++, count++)
        {
            value += f(a, i, j)*count;
        }
    }
    return value;
} 

I was told to precalculate some values, and its time complexity can be reduced to O(n) by ChatGPT.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This problem is "D. Sum of XOR Functions" by the way. Some people have posted solutions for it online. \$\endgroup\$
    – user555045
    Commented Oct 5, 2023 at 9:57

5 Answers 5

7
\$\begingroup\$
  • long long int main() invokes UB. main must be declared as int.

  • long long is an overkill. It is guaranteed that \$0 \le a_i \le 10^9\$. Recall that \$2^{10} = 1024\$ is slightly larger than \$10^3\$, so \$10^9\$ is surely less than \$2^{30}\$. All \$a_i\$, and all XORs, comfortably fit into a 32-bit-wide type.

    So do the indices.

  • Intermediate values computed in sum may overflow. You need to use addition (and multiplication) modulo 998244353.

  • Computing \$f\$ takes \$O(n)\$ times. Computing it in the double loop drives the time complexity to \$O(n^3)\$.

    It is worth noticing that we have \$x \oplus x = 0\$ and \$x \oplus 0 = x\$. It means that \$f(l, r) = f(0, r) \oplus f(0, l-1)\$. In other words, you only need to compute cumulative XORs - in \$O(n)\$ time - to reduce the overall time complexity to \$O(n^2)\$.

    I don't know how to reduce it further. XOR does not interact nicely with neither addition nor multiplication. I will be very surprised to see an \$O(n)\$ solution.

\$\endgroup\$
3
  • \$\begingroup\$ "long long int main() invokes UB. main must be declared as int." may be OK given the C spec's "or in some other implementation-defined manner." C23dr § 5.1.2.2.1 1 \$\endgroup\$ Commented Oct 7, 2023 at 13:53
  • 1
    \$\begingroup\$ If "long long is an overkill.", perhaps post an alternative. long? \$\endgroup\$ Commented Oct 7, 2023 at 13:55
  • \$\begingroup\$ @chux-ReinstateMonica I think 32-bit-wide type is enough of an alternative. int32_t shall be good. \$\endgroup\$
    – vnp
    Commented Oct 7, 2023 at 15:47
7
\$\begingroup\$

Choosing int as the return type for main() for portability and compatibility":

Portably, main() only returns int. Best to return an int and not a long long.

// long long int main ()
int main(void)

Do not cast the result of malloc and family:

// long long int *a = (long long int *)malloc(n*sizeof(long long int));
   long long int *a = malloc (n * sizeof a[0]);

malloc() returns a generic void * that is implicitly converted to any other pointer type. As such, its result need not be casted and only serves to clutter one's code.

Check the return value of library functions:

If a function be advertised to return an error code in the event of difficulties, thou shalt check for that code, yea, even though the checks triple the size of thy code and produce aches in thy typing fingers, for if thou thinkest "it cannot happen to me", the gods shall surely punish thee for thy arrogance.The Ten Commandments For C Programmers

malloc() and family returns NULL to indicate failure. Failure to check it risks invoking undefined behavior by a subsequent NULL pointer dereference.

// What does a stand for?
long long int *a = malloc (n * sizeof a);

if(!a) { 
   complain();
}

scanf() returns the number of conversions successfully performed. We ought to check its return value to ensure that we did indeed read a long long int.

if(scanf("%lld", &n) != 1) {
   complain();
}

Use const:

The parameters that are not changed anywhere in the function should be const-qualified.

// Again, what do a, n1, and n2 stand for?
static long long int f(const long long int *a , long long int n1, long long int n2)

sum() and f() should have static linkage:

As the functions are only used in this translation unit, they should be declared with having internal linkage:

// long long int f(long long int *a,long long int b, long long int c);
// long long int sum(long long int arraysize, long long int*a);

// What do f, a, b, and c stand for?
static long long int f(long long int *a, long long int b, long long int c);
static long long int sum(long long int arraysize, long long int *a);

Naming and formatting:

Function and variable names should be descriptive and meaningful, providing clarity to readers. Using cryptic or overly short names, such as f for a function or a, b, and c for variables, can hinder comprehension and should be avoided.

Choose a consistent strategy for whitespace and other text formatting. I suggest using an code formatter like GNU indent.

Minor:

We can eliminate redundant forward declarations by defining the functions before main().

\$\endgroup\$
0
5
\$\begingroup\$

Efficiency only answer

Rather than recalculate f(l, r) repeatedly, recognize that f(l, r) is the same as f(0, l-1) ^ f(0, r) and so form a table xor[r+1].

It is much faster.


Illustrative code

#include <stdlib.h>
#include <stdint.h>

uint32_t bitwise_f(const uint32_t *a, size_t left, size_t right) {
  uint32_t c = 0;
  for (size_t i = left; i <= right; i++) {
    c = c ^ a[i];
  }
  return c;
}

uint32_t bitwise_sum(size_t n, const uint32_t a[n]) {
// or
//  uint32_t bitwise_sum(size_t n, uint32_t *a) {
  uint64_t sum = 0;
  for (size_t left = 0; left < n; left++) {
    uint64_t count = 1;
    for (size_t r = left; r < n; r++) {
      sum += bitwise_f(a, left, r) * count;
      sum %= 998244353u;
      count++;
    }
    sum %= 998244353u;
  }
  return (uint32_t) sum;
}

uint32_t bitwise_sum_alt(size_t n, const uint32_t a[n]) {
  uint32_t xor[n+1];
  uint32_t c = 0;
  xor[0] = c;
  for (size_t i = 0; i < n; i++) {
    c = c ^ a[i];
    xor[i+1] = c;
  }

  uint64_t sum = 0;
  for (size_t left = 0; left < n; left++) {
    uint64_t count = 1;
    for (size_t right = left; right < n; right++) {
      sum += (xor[right + 1 ] ^ xor[left]) * count;
      count++;
      sum %= 998244353u;
    }
    // sum %= 998244353u;
  }
  return (uint32_t) sum;
}

// Test code
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define BITWISE_NO_EXPECT -1

double bitwise_test(int64_t expected_sum, size_t n, const uint32_t a[n]) {
  clock_t start = clock();
  uint32_t sum = bitwise_sum_alt(n, a);
  clock_t end = clock();
  double cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
  printf("Sum:%" PRIu32 " ", sum);
  printf("f() took %f seconds to execute. \n", cpu_time_used);
  if (expected_sum != BITWISE_NO_EXPECT && sum != expected_sum) {
    printf("sum:%" PRIu32 " does not equal expected:%" PRIi64 "\n", //
        sum, expected_sum);
  }
  return cpu_time_used;
}

void bitwise_test_large(size_t nmax) {
  for (size_t n = 64; n <= nmax; n *= 2) {
    uint32_t *a = malloc(sizeof a[0] * n);
    assert(a);
    for (size_t i = 1; i < n; i++) {
      a[i] = (uint32_t) rand();
    }
    printf("Size:%zu  ", n);
    bitwise_test(BITWISE_NO_EXPECT, n, a);
    fflush(stdout);
  }
}

int main(void) {
#if 1
  bitwise_test(12, 3, (uint32_t[]) {1, 3, 2});
  bitwise_test(1337, 4, (uint32_t[]) {39, 68, 31, 80});
  bitwise_test(257421502, 7, (uint32_t[]) {313539461, 779847196, 221612534,
          488613315, 633203958, 394620685, 761188160});
    bitwise_test_large(1u << 18);
  return 0;
#endif
  size_t n;
  scanf("%zu", &n);
  uint32_t *a = malloc(sizeof a[0] * n);
  assert(a);
  for (size_t i = 0; i < n; i++) {
    scanf("%" SCNu32, a + i);
  }
  bitwise_test(BITWISE_NO_EXPECT, n, a);
  free(a);
}

Output with bitwise_sum() (OP's approach)

Sum:12 f() took 0.000000 seconds to execute. 
Sum:1337 f() took 0.000000 seconds to execute. 
Sum:257421502 f() took 0.000000 seconds to execute. 
Size:64  Sum:201216235 f() took 0.000000 seconds to execute. 
Size:128  Sum:935200203 f() took 0.000000 seconds to execute. 
Size:256  Sum:236376682 f() took 0.000000 seconds to execute. 
Size:512  Sum:702872695 f() took 0.016000 seconds to execute. 
Size:1024  Sum:564088685 f() took 0.031000 seconds to execute. 
Size:2048  Sum:144981798 f() took 0.313000 seconds to execute. 
Size:4096  Sum:855006432 f() took 2.328000 seconds to execute. 
Size:8192  Sum:627587314 f() took 18.359000 seconds to execute. 
Size:16384  Sum:777920909 f() took 145.171000 seconds to execute. 
...
 

Output with bitwise_sum_alt() that uses a table look-up

Sum:12 f() took 0.000000 seconds to execute. 
Sum:1337 f() took 0.000000 seconds to execute. 
Sum:257421502 f() took 0.000000 seconds to execute. 
Size:64  Sum:201216235 f() took 0.000000 seconds to execute. 
Size:128  Sum:935200203 f() took 0.000000 seconds to execute. 
Size:256  Sum:236376682 f() took 0.000000 seconds to execute. 
Size:512  Sum:702872695 f() took 0.000000 seconds to execute. 
Size:1024  Sum:564088685 f() took 0.000000 seconds to execute. 
Size:2048  Sum:144981798 f() took 0.016000 seconds to execute. 
Size:4096  Sum:855006432 f() took 0.000000 seconds to execute. 
Size:8192  Sum:627587314 f() took 0.047000 seconds to execute. 
Size:16384  Sum:777920909 f() took 0.109000 seconds to execute. 
Size:32768  Sum:227211329 f() took 0.609000 seconds to execute. 
Size:65536  Sum:538845010 f() took 2.407000 seconds to execute. 
Size:131072  Sum:913595480 f() took 9.640000 seconds to execute. 
Size:262144  Sum:776716501 f() took 38.749000 seconds to execute. 

Possible other simplifications exists.

\$\endgroup\$
3
\$\begingroup\$

Offset from 0 or 1?

Keep in mind the posted algorithm uses array indexing from 1 and C uses offsets from 0.

As I see it, OP has done that correctly.

Array size type

Use size_t for array sizing and indexing. long long is likely unnecessarily wide. Using size_t also conveys the idea that the object is for indexing/sizing.

#include <stdlib.h>
// long long int f(long long int *a,long long int b, long long int c);
long long int f(long long int *a, size_t b, size_t c);

Handle unexpected values

A more generic form of f() would behave well even if l > r (n1 > n2).

// long long int c = a[n1];
long long int c = 0;
// for (long long int i = n1+1; i <=n2; i++)
for (long long int i = n1; i <=n2; i++)
  ...

This matches posted formula better.

Use const for refenced data

Its faster (with weak compilers), Allows calling on const arrays and 3) conveys the constant idea of data being processed.

// long long int f(long long int *a, ...) {
long long int f(const long long int *a, ...) {

Save long long for intermediate calculations

Improve speed by using narrower types when possible. (If on a smaller than 64-bit machine.)

// long long int f(long long int *a,long long int n1, long long int n2) {
//    long long int c = a[n1];
//    for (long long int i = n1+1; i <=n2; i++)

uint32_t int f(const uint32_t *a, size_t n1, size_t n2) {
    uint32_t c = 0;
    for (size_t i = n1; i <=n2; i++)

Less common function names

Consider you code may get used in a larger program. Names like f, sum will certainly collide.

// f
bitwise_f  // example

Consider unsigned types for problems involving logical operations

Consider types that fit the range of the problem

With 0≤a[i]≤1,000,000,000), a[i] fits in a 32-bit integer like uint32_t.

Improve presentation

Use an auto-formatter for code.

Cleaner for()

Avoid packing code in for() statements.


Putting the above together (and some other ideas)

#include <stdlib.h>
#include <stdint.h>

uint32_t bitwise_f(uint32_t *a, size_t left, size_t right) {
  uint32_t c = 0;
  for (size_t i = left; i <= right; i++) {
    c = c ^ a[i];
  }
  return c;
}

uint32_t bitwise_sum(size_t n, uint32_t a[n]) {
// or
//  uint32_t bitwise_sum(size_t n, uint32_t *a) {
  uint64_t sum = 0;
  for (size_t left = 0; left < n; left++) {
    uint64_t count = 1;
    for (size_t right = left; right < n; right++) {
      // Note 64-bit multiplication and addition.
      sum += bitwise_f(a, left, right) * count;
      sum %= 998244353u;
      count++;
    }
  }
  return (uint32_t) sum;
}
\$\endgroup\$
3
  • \$\begingroup\$ The usual reminder that uint32_t is an optional type; I recommend uint_fast32_t for pedantic portability. Best to localise the choice to a single typedef in case of changing mind again later... \$\endgroup\$ Commented Oct 8, 2023 at 12:43
  • \$\begingroup\$ @TobySpeight Agree about typedef. With singleton objects, uint_fast32_t is better than uint_least32_t. With arrays, uint_least32_t can readily outperform uint_fast32_t due to better caching of the smaller object - for the rare cases they are, in fact, different. \$\endgroup\$ Commented Oct 8, 2023 at 13:16
  • \$\begingroup\$ Yes, "fast" seems more appropriate than "least" here. \$\endgroup\$ Commented Oct 8, 2023 at 18:04
1
\$\begingroup\$

Efficiency

As noted in other answers, your code takes \$O(n^3)\$ time to run. It can be reduced to \$O(n^2)\$ by computing the cumulative XOR, but that's still quite slow for \$n \approx 3\cdot10^5\$. The problem can be solved in \$O(n \log U)\$ time, where \$U\$ is the maximum element in the array, and it's probably what the author of it intended:

If we split each number \$a_i\$ to its bits, \$a_i = b_i^0 + 2b_i^1 + 2^2 b_i^2 + 2^3 b_i^3 + ...\$, we can define \$f_j(l,r) = b_l^j \oplus b_{l+1}^j \oplus \cdots \oplus b_{r}^j \$, and notice that \$f(l, r) = f_0(l, r) + 2 f_1(l, r) + 2^2 f_2(l, r) + \cdots\$. Therefore $$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) (r-l+1) = \sum_{j=0}^{\log_2(U)}{2^j \sum_{l=1}^{n} \sum_{r=l}^{n} f_j(l, r) (r-l+1)}$$ And we reduced the problem to \$\log U\$ problems where \$a_i \in \{0 , 1\}\$.

To solve the problem when \$a_i \in \{0, 1\}\$, we can define \$b_i\$ (for \$0 \leq i \leq n\$) to be the xor of the first \$i\$ values of \$a\$, as in the other answers. If we do that, we have $$\sum_{l=1}^n \sum_{r=l}^n f(l, r) (r-l+1) = \sum_{l=0}^{n-1} \sum_{r=l+1}^{n} (b_l \oplus b_r) (r - l) = \sum_{l=0}^{n-1} (\sum_{r=l+1}^{n} (b_l \oplus b_r) r - l \sum_{r=l+1}^{n} (b_l \oplus b_r))$$

to calculate this, we can maintain \$\sum_{r=l+1}^{n} b_r, \sum_{r=l+1}^{n} (1\oplus b_r), \sum_{r=l+1}^{n} r b_r, \sum_{r=l+1}^{n} r (1\oplus b_r)\$ as we iterate over the array.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.