in Written Exam recategorized by
384 views
3 votes
3 votes

Read the C code given below. What would be the output of the
following program? Justify your answer.


 

#include <stdio.h>
int myrecurse(int a, int b){
    return (b == 1 ? a: myrecurse(a, b-1) + a);
}
main() {
    int a[]= {2,3,4,5,6};
    int i, x;
    for (i = sizeof(a)/sizeof(*a), x = 0; --i; )
    x += myrecurse(*(a+i), a[i-1]);
    printf("\nThe result is: %d", x);
}


(b) Suppose you are given a sequence $S = < x_1, x_2, . . . , x_n >$  of  $n$ integers. For $1 ≤ i ≤ j ≤ n$, the sequence $< x_i, x_{i+1},.. . . , x_j >$ of consecutive elements is called a subsequence of S. The sum of a subsequence is the sum of the integers in that subsequence. Give an $O(n log n)$ algorithm to determine whether the given sequence $S$ has a subsequence whose sum is zero, and justify the correctness of the algorithm.

in Written Exam recategorized by
384 views

1 Answer

3 votes
3 votes
Best answer

(a)

https://gateoverflow.in/124805/c-programming 



(b)

$N$ time binary search = $N\log N$


#include <bits/stdc++.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef struct {
	int sum_val;
	int pos;
}T;
bool compare(T a,T b) {
	return (a.sum_val < b.sum_val);
}
int binary_search(T *tuple,int key,int p,int n) {
	int l = 0,r = n;
	while(l<r) {	
		int mid = (l+r)/2;
		if(tuple[mid].sum_val == key && tuple[mid].pos < p) {
			return tuple[mid].pos;
		}else if(tuple[mid].sum_val <= key) {
			l = mid+1;
		}else {
			r = mid-1;
		}
	}
	return -1;
}
int main() {
	int a[] = {9,2,2,3,-4,-1,2,4,5};
	int n = sizeof(a)/sizeof(*a);
	T *tuple = (T*)(malloc(n*sizeof(T)));
	int sum = 0;
	for(int i=0;i<n;i++) {
		sum += a[i];
		tuple[i].sum_val = sum;
		tuple[i].pos = i; 	
	}
	sort(tuple,tuple+n,compare);
	int start,end;
	bool found = false;
	sum = 0;
	for(int pos=0;pos<n;pos++) {
		sum += a[pos];
		int res = binary_search(tuple,sum,pos,n);
		if(res != -1) {
			printf("Found between %d and %d \n",res+1,pos);
			found = true;
			break;
		}
	}
	if(!found) printf("NOT found\n");

	// free 
	for(int i=0;i<n;i++) {
		free((void *)(tuple+i));
	}
	free(tuple);
	return 0;
}

output :

Found between 2 and 5
selected by
by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true