Lesson 3: GenomicRangeQuery (Genomic Range Query)

This is another 'running total' problem.

The strategy is to scan the string S once to memorize
each running total of ACGT at the position.

For instance, if the totals of ACGT  are [4,2,3,1] at the index 'p' and [4,5,5,1] at the index 'q' (p <= q), we can say that there is no A and T found between p and q, because the total numbers of A and T stay the same. On the other hand, we can say there are C and D, the total numbers of C and G are increased.

The code below implements this strategy. We allocate the N + 1 size array so that we can simplify the code.

The code gives the score of 100%.

--------------------------------
SOLUTION
--------------------------------
struct Results solution(char *S, int P[], int Q[], int M) 
{
    typedef struct ACGT {
        int a;
        int c;
        int g;
        int t;
    } ACGT;
    
    int N = strlen(S);
    ACGT* acgt = calloc(sizeof(ACGT), (N + 1));
    
    int i;
    int a = 0;
    int c = 0;
    int g = 0;
    int t = 0;

    //count the numbers of ACGT. 
    for (i = 0; i < N; i++){
        switch(S[i]){
            case 'A':
                a++;
                break;
            case 'C':
                c++;
                break;
            case 'G':
                g++;
                break;
            case 'T':
                t++;
                break;
            default:
                exit(-1);
        }
        //we leave acgt[0] untouched (filled with zero)
        //so that we can simplify the next step.
        acgt[i + 1].a = a;
        acgt[i + 1].c = c;
        acgt[i + 1].g = g;
        acgt[i + 1].t = t;
    }
    
    
    struct Results result;
    
    result.A = calloc(sizeof(int), M);
    result.M = M;
    
    for (i = 0; i < M; i++){
        ACGT s = acgt[P[i]];
        ACGT e = acgt[Q[i] + 1];
        if (e.a - s.a > 0){
            result.A[i] = 1;
        }
        else if (e.c - s.c > 0){
            result.A[i] = 2;
        }
        else if (e.g - s.g > 0){
            result.A[i] = 3;
        }
        else {
            result.A[i] = 4;
        }
    }
    
    
    free(acgt);
    
    return result;
}