CareerCup

assuming ur response is to my solution, the lowest sum above the threshold would make sure that the window is minimal in length. Just pick the window with the minimal size and that is your answer. I think its elaborate enough for you to understand now!!

// 2,1,1,4,3,6
// sum = 8

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

struct window {
	int l;
	int r;
	int s;
};

typedef struct window window_t;
int main () {
	window_t w, ans;
	int A[] = {2, 1, 1, 4, 0, 1, 4};
	int sum = 6;
	int len_a = sizeof(A)/sizeof(int);
	memset(&w, 0, sizeof(w));
	// set window
	while (w.s <= sum) {
		w.s += A[w.r];
		w.r++;
	}
	w.r--;
	// set window from behind
	while (w.s > sum) {
		w.s -= A[w.l];
		w.l++;
	}
	w.l--;
	w.s += A[w.l];
	int min_l = w.r - w.l + 1;
	memcpy(&ans, &w, sizeof(w));
	for (int i = w.r+1; i < len_a; i++) {
		w.s += A[i];
		w.r++;
		while (w.s > sum) {
			w.s -= A[w.l];
			w.l++;
		}
		w.l--;
		w.s += A[w.l];
		if (min_l > w.r - w.l + 1) {
			memcpy(&ans, &w, sizeof(w));
			min_l = w.r - w.l + 1;
		}
	}	
	printf ("l = %d, r = %d, s = %d, min_l = %d\n", ans.l, ans.r, ans.s, min_l);
	printf ("The corresponding elements in the sequence are : {");
	for (int i = ans.l; i <= ans.r; i++) printf ("%d, ", A[i]);
	printf("}\n"); 
}

Right now my code maintains the invariant that the sum inside the window after every iteration is greater than the given sum and is the window is "tight" from both the ends.

This solution won't work for negative numbers as the invariant fails in that case. There should be a simple modification to maintain that invariant. I will update soon.

EDIT :
This modification maintains the invariant as mentioned above and the solution should work for negative numbers as well.

// 2,1,1,4,3,6
// sum = 8

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

struct window {
	int l;
	int r;
	int s;
};

typedef struct window window_t;
int main () {
	window_t w, ans;
	int A[] = {2, 1, 1, 4, 0, 1, 4};
	int sum = 6;
	int len_a = sizeof(A)/sizeof(int);
	memset(&w, 0, sizeof(w));
	// set window from the front
	while (w.s <= sum) {
		w.s += A[w.r];
		w.r++;
	}
	w.r--;
	// set window from behind
	while (w.s > sum) {
		w.s -= A[w.l];
		w.l++;
	}
	w.l--;
	w.s += A[w.l];
	int min_l = w.r - w.l + 1;
	memcpy(&ans, &w, sizeof(w));
	for (int i = w.r+1; i < len_a; i++) {
		w.s += A[i];
		w.r++;
		if (w.s <= sum) {
			// we encountered a negative number which reduces w.s to become smaller than/ equal to sum
			// keep adding numbers until you are able to make sure that w.s > sum
			while (w.s <= sum) {
				w.s += A[w.r];
				w.r++;
				i++;
			}
			w.r--;
			i--;
		}
		while (w.s > sum) {
			w.s -= A[w.l];
			w.l++;
		}
		w.l--;
		w.s += A[w.l];
		if (min_l > w.r - w.l + 1) {
			memcpy(&ans, &w, sizeof(w));
			min_l = w.r - w.l + 1;
		}
	}	
	printf ("l = %d, r = %d, s = %d, min_l = %d\n", ans.l, ans.r, ans.s, min_l);
	printf ("The corresponding elements in the sequence are : {");
	for (int i = ans.l; i <= ans.r; i++) printf ("%d, ", A[i]);
	printf("}\n"); 
}

a basic O(log(b)) solution, assuming the result shall fit in a long long. Otherwise we have to implement a method for string multiplication.

#include <iostream>

using namespace std;

computeApowB(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if (b & 1) {
			ret *= a;
		}		
		a = a * a;
		b /= 2;
	}
}

sol1. First sort the array, then swap pairs of numbers.
sol2. Traverse the array starting from the first vertex till the second last vertex, when at an even position swap the value with the next position if the former is smaller; when at an odd position swap the value with the next position is the former is larger

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int main () {
	int A[] = {1,2,3,4,5,6};
	
	// solution 1, O(nlog(n))
	int len_a = sizeof(A)/sizeof(int);
	sort(A, A+len_a);
	for (int i = 0; i < len_a; i+=2) {
		swap(A[i], A[i+1]);
	}
	cout << "{";
	for (int i = 0; i < len_a; i++) cout << A[i] << ", ";
	cout << "}" << endl;
	
	// solution 2 O(n)
	for (int i = 0; i < len_a-1; i++) {
		if (i & 1) {
			if (A[i] > A[i+1]) swap(A[i], A[i+1]);
		}
		else {
			if (A[i] < A[i+1]) swap(A[i], A[i+1]);
		}
	}
	
	cout << "{";
	for (int i = 0; i < len_a; i++) cout << A[i] << ", ";
	cout << "}" << endl;
}

Isn't this an oral question.

You divide the rod in

(int) N / 6

pieces of 6. Then for the remaining

N % 6

pieces devide as follows

1 -- 1
2 -- 2
3 -- 3
4 -- 2, 2
5 -- 2, 3

+1