#include <stdio.h>
#include <string.h>
/*
Algo:
Find the postion of the last character from the beginning
if pos > mid return 0
else
rotationlength is the index of p and check whether the string satisfies the rotation with the rotation length
*/
int isPowStr(const char *str) {
int len = strlen(str);
const char *end = str + len - 1;
const char *mid = str + len / 2;
//find the postion of the last charater from the beginning
const char *p = strchr(str, *end);
//while the postion of the last character <= mid (no of repetitions >= 2)
while(p <= mid) {
int found = 1;
int rotlen = p - str + 1;
const char *s = p;
//check whether rotlen satiesfies
while(p >= str && found) {
const char *q = p + rotlen;
do{
if(*q != *p) {
found = 0;
break;
}
q += rotlen;
} while(q <= (end - (s - p))) ;
p--;
}
if(found)
return 1;
p = strchr(s + 1, *end);
}
return 0;
}
int main() {
char str[64];
scanf("%s", str);
printf("%d\n", isPowStr(str));
return 0;
}
Monthly Archives: March 2011
Maximum product of a consecutive sequence of an array of integers without zero
Problem
#include <stdio.h>
typedef struct {
int start, end, product;
}Ret;
Ret maxProduct(int a[], int n) {
Ret r = {0, n - 1, 1};
int i = n, j, p1, p2;
while(i--)
r.product *= a[i];
if(r.product > 0)
return r;
//need to eliminate one negative number at the beginning or at the end
p1 = p2 = r.product;
for( i = 0 ; i < n && a[i] > 0; ++i)
p1 /= a[i];
p1 /= a[i];
for(j = n -1; j >= 0 && a[j] > 0; --j)
p2 /= a[j];
p2 /= a[j];
if(p1 >= p2) {
r.start = i + 1;
r.product = p1;
} else {
r.end = j - 1;
r.product = p2;
}
return r;
}
int main() {
int n;
scanf("%d", &n);
int a[n];
int i;
for(i = 0; i <n; ++i)
scanf("%d", a + i);
Ret r = maxProduct(a, n);
printf("%d %d %d\n", r.start, r.end, r.product);
return 0;
}
Given an unsorted array and two numbers, find the minimum distance between them. For example, if the array is {1,2, 10, 2, 3, 5, 2, 1, 5} distance between 2 and 5 is 1
#include <stdio.h>
#include <algorithm>
#include <limits.h>
int minDist(int a[], int n, int b, int c) {
int ret = INT_MAX, cur = -1;
while(n--) {
if(a[n] == b || a[n] == c) {
if(cur != -1 && a[cur] != a[n]) {
ret = std::min(ret, cur - n);
}
cur = n;
}
}
return ret;
}
int main() {
int a[] = {1, 2, 10, 2, 3, 5, 2, 1, 5};
printf("%d\n", minDist(a, sizeof(a)/sizeof(int), 2, 5));
return 0;
}
deleting a node in singly linked list if it is less than any of the successor nodes
Problem
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
}Node;
typedef Node *list;
typedef struct {
list l;
int m;
}Ret;
Ret del(list l, Node *prev) {
Ret r = {NULL, 0};
if(l == NULL)
return r;
r = del(l->next, l);
if(r.m > l->data) {
if(prev)
prev->next = r.l;
free(l);
} else {
r.m = l->data;
r.l = l;
}
return r;
}
list append(list l, int n) {
Node * node = calloc(sizeof(Node), 1);
node->data = n;
if(l == NULL)
return node;
list ret = l;
while(l->next)
l = l->next;
l->next = node;
return ret;
}
void print(list l){
while(l) {
printf("%d ", l->data);
l = l->next;
}
printf("\n");
}
int main() {
int a[] = {7, 4, 8, 5, 2, 7, 3, 6};
int i;
list l = NULL;
for(i = 0; i < sizeof(a)/sizeof(int); ++i)
l = append(l, a[i]);
Ret r = del(l, NULL);
print(r.l);
}
Given an array of Integers, if u are on ith element u can make max arr jumps. If i am at an element with value zero, i cannot move forward. find the least selection to reach end of the array.
/*
Algo:
Lets define a function called hop which is number of steps required to reach the end of array from the given position, So
hop(i) = INT_MAX if a[i] == 0
hop(i) = 1 + min(hop(j) where j is from i + 1 to i + a[i]
hop(0) is the required answer
*/
#include <stdio.h>
#include <limits.h>
int minhops(int a[], int n) {
int hop[n] ;
int i = n;
while(i--) {
if(a[i] == 0)
hop[i] = INT_MAX;
else {
if(i + a[i] >= n)
hop[i] = 1;
else {
int j, min = INT_MAX;
for(j = i + a[i]; j > i; --j){
if(hop[j] < min)
min = hop[j];
}
hop[i] = min + 1;
}
}
}
return hop[0];
}
int main() {
int a[] = {1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
int n = minhops(a, 11);
if(n != INT_MAX)
printf("%d\n", minhops(a, 11));
return 0;
}
Find the smallest window in a string containing all characters of another string
#include <stdio.h>
typedef struct {
const char *start, *end;
}Window;
static int isAllPresent(int a[]) {
int i;
for(i = 0; i < 128; ++i)
if(a[i] != 0 && a[i] != -1)
return 0;
return 1;
}
Window minWindow(const char *haystack, const char *needle) {
Window r = {NULL, NULL}, cur;
int count[128], i;
const char *p = needle;
char c;
/*
find the count of the chars in needle
*/
for(i = 0; i < 128; ++i)
count[i] = -1;
while((c = *p++)) {
i = count[c];
count[c] = ((i == -1) ? 1 : (i + 1));
}
//find the first character of the needle in haystack
while((c = *haystack)){
if(count[c] != -1) break;
haystack++;
}
if(c == '') return r;
cur.start = haystack;
while((c = *haystack) ) {
if(count[c] != -1) { //if it presents
if(count[c] == 0){//this char count is zero, then we have to skip upto the same character in window
p = cur.start;
while(*p != c) { //till the current character not find
if(count[*p] != -1) {
count[*p]++;
}
p++;
}
p++; //move to the next char
while(p < haystack && count[*p] == -1 ) { //find the first character persents in needle
p++;
}
cur.start = p;
} else { //we can accomdate this character
count[c]--;
}
if(count[c] == 0 && isAllPresent(count)) { //if the window has all the chars of needle
cur.end = haystack;
if(r.start == NULL || (r.end - r.start) > (cur.end - cur.start))
{
r = cur;
}
}
}
haystack++;
}
return r;
}
int main() {
Window r = minWindow("this is a test string", "tsist ");
if(r.start) {
while(r.start <= r.end) {
printf("%c", *r.start);
r.start++;
}
printf("\n");
}
return 0;
}
Effective Programming 