To find whether the given string is repetition of a substring

#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;
}
Advertisements

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;
}