mayankme0077
BAN USER// 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");
}

mayankme0077
April 26, 2014 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;
}
}

mayankme0077
April 26, 2014 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_a1; 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;
}

mayankme0077
April 25, 2014 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

mayankme0077
October 15, 2012 +1
 mayankme0077 October 15, 2012
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!!
 mayankme0077 April 27, 2014