Birthday Gift

QUESTION

Today is Kriti’s birthday but I forgot to bring a gift for her. She is very angry with me. I have an idea for a gift. She likes coding very much. Why not give her a problem to solve as her gift?\n\nI know a problem but I am not sure whether its solvable or not.\n\nThe problem initially has N strings numbered 1 to N. The program has to answer Q queries. Each query is of the form l r S. For each query, the program has to print the number of times the string S appears in the range [l,r].Help me by solving the problem!!\n\n\nInput\n\nInput will begin with an integer N denoting the number of strings.\nN lines follows each having a string. \nThe next line contains Q denoting the number of queries.\nEach of the next Q lines contain a query of the form l r S.\n\nOutput\nFor each query of type l r S, print the answer to that query. Each answer must be in a new line.

“TESTCASE_1”: “3\nabc\ndef\nabc\n3\n1 2 abc\n1 3 abc\n1 2 hgj\n###—###SEPERATOR—###—\n1\n2\n0”, “TESTCASE_2”: “5\nefdfgcfe\nfggbfgdg\nfggbfgdg\nceggcb\nfggbfgdg\n3\n1 3 dbacgbgfc\n1 2 ccbbf\n1 3 gcdfeecdb\n###—###SEPERATOR—###—\n0\n0\n0”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<stdio.h>
#include<string.h>
 
typedef struct node{
	int index;
	char string[15];
}Node;
 
void merge(Node arr[], int l, int m, int r)
{
	Node arr1[m-l+1], arr2[r-m];
	int i, j, k;
 
	for(i = 0; i < m-l+1; i++)
		arr1[i] = arr[l+i];
 
	for(j = 0; j < r-m; j++)
		arr2[j] = arr[j+m+1];
 
	i = 0;
	j = 0;
	k = l;
 
	while((i< m-l+1) && (j < r-m))
	{
		if(strcmp(arr1[i].string, arr2[j].string) < 0)
		{
			arr[k++] = arr1[i++];
		}
		
		else if(strcmp(arr1[i].string, arr2[j].string) == 0)
		{
			if(arr1[i].index < arr2[j].index)
			{
				arr[k++] = arr1[i++];
			}
			else
			{
				arr[k++] = arr2[j++];
			}
		}
		else
		{
			arr[k++] = arr2[j++];
		}
	}
 
	while(i < m-l+1)
	{
		arr[k++] = arr1[i++];
	}
	while(j < r - m)
	{
		arr[k++] = arr2[j++];
	}
 
}
 
void mergesort(Node arr[], int l, int r)
{
	if(l < r){
		int m = l + (r - l)/2;
		mergesort(arr, l , m);
		mergesort(arr, m+1, r);
		merge(arr, l, m, r);
	}
}
 
int main()
{
	int n, q, i, j, l, r, l1, r1, lf, rf, m;
	char s[15];
	Node arr[100001];
 
	scanf("%d", &n);
 
	for(i = 0; i < n; i++)
	{
		scanf("%s", arr[i].string);
		arr[i].index = i;
	}
 
	mergesort(arr, 0, n-1);
	
	scanf("%d", &q);
 
	for(i = 0; i < q; i++)
	{
		scanf("%d %d %s", &l, &r, s);
 
		l--;
		r--;
 
		l1 = 0;
		r1 = n-1;
		lf = -1;
		rf = -1;
 
		while(l1 <= r1)
		{
			m = l1 + (r1-l1)/2;
 
			if(strcmp(arr[m].string, s) == 0)
			{
				if(l <= arr[m].index && arr[m].index <= r)
				{
					if((m-1 < 0) || (strcmp(arr[m-1].string, s) == 0 && l > arr[m-1].index) || (strcmp(arr[m-1].string, s) != 0))
					{
						lf = m;
						break;
					}
					else
					{
						r1 = m-1;
					}
				}
 
				else if(l > arr[m].index)
					l1 = m+1;
 
				else if(r < arr[m].index)
					r1 = m-1;
			}
 
			else if(strcmp(arr[m].string, s) < 0)
			{
				l1 = m+1;
			}
 
			else if(strcmp(arr[m].string, s) > 0)
			{
				r1 = m-1;
			}
		}
 
		if(lf != -1)
		{
			l1 = 0;
			r1 = n-1;
			while(l1 <= r1)
			{
				m = l1 + (r1-l1)/2;
 
				if(strcmp(arr[m].string, s) == 0)
				{
					if(l <= arr[m].index && arr[m].index <= r)
					{
						if((m+1 >= n) || (strcmp(arr[m+1].string, s) == 0 && r < arr[m+1].index) || (strcmp(arr[m+1].string, s) != 0))
						{
							rf = m;
							break;
						}
 
						else
						{
							l1 = m+1;
						}
					}
 
					else if(l > arr[m].index)
						l1 = m+1;
 
					else if(r < arr[m].index)
						r1 = m-1;
				}
 
				else if(strcmp(arr[m].string, s) < 0)
				{
					l1 = m+1;
				}
 
				else if(strcmp(arr[m].string, s) > 0)
				{
					r1 = m-1;
				}
			}
 
			printf("%d\n", rf - lf + 1);
		}
 
		else
			printf("0\n");
	}
 
	return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro