/********************************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : LT-2-EVEN-B
* Description : Find Number of Ones from K1-th position
                to K2-th position in N-th Row (+ print)
********************************************************/

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

/* recursively searches the k-th symbol present in n-th row expansion */
int kthSymbol(unsigned int n, unsigned long long int k)
{
    if (n == 1) {
        return 0;
    }
    if (k % 2 == 0) {
        if (kthSymbol(n - 1, k / 2) == 0) {
            return 0;
        }
        else {
            return 1;
        }
    }
    else {
        if (kthSymbol(n - 1, (k + 1) / 2) == 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}

/* prints the expanded rows */
void printRows(unsigned int n)
{
    unsigned int l;
    unsigned long long int i, j, rowLength;
    char *rowStr;
    
    rowStr = (char *)malloc(pow(2,n)*sizeof(char));
    printf("\n++ The 1-th Row: 0");
    rowStr[0] = '1';
    rowStr[1] = '0';
    rowStr[2] = '\0';
    printf("\n++ The 2-th Row: %s", rowStr);
    for(l=2; l<n; l++) {
        rowLength = strlen(rowStr);
        i = rowLength; j = 2*i-1;
        while(1) {
            if(rowStr[i-1] == '0') {
                rowStr[j-1] = '1';
                rowStr[j] = '0';
            }
            else { // if (rowStr[i-1] == '1')
                rowStr[j-1] = '0';
                rowStr[j] = '1';
            }
            if(j == 1 || j == 2) break;
            j = j-2; i--;
        }
        rowStr[2*rowLength] = '\0';
        printf("\n++ The %u-th Row: %s", l+1, rowStr);
    }
}

int main()
{
    unsigned int n;
    unsigned long long int k1, k2, k, count1=0;

    printf("Enter n: ");
    scanf("%u", &n);
    printf("Enter k1: ");
    scanf("%llu", &k1);
    printf("Enter k2: ");
    scanf("%llu", &k2);
    
    printRows(n);

    for(k=k1; k<=k2; k++) {
        if(kthSymbol(n,k) == 1) {
            count1 ++;
        }
    }
    printf("\n\n++ The Number of 1s from %llu-th index to %llu-th Index in Row %u is: %llu\n", k1, k2, n, count1);

    return 0;
}