Java : maximum sum of three adjacent elements in a list

Problem : Given a list of Integers,Find the tuple of 3 adjacent elements in this list that adds up to the maximum sum.

Reference : http://www.careercup.com/question?id=3373955

Solution : complexity O(n)

Program:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
*/
package careercup.google;

/**
 *
 * @author Harit
 */
public class AdjacentSum {

    //private static int[] input = new int[]{1,0,2,3,0,1,2,3};
    private static int[] input = new int[]{5,6,9,2,8,7,6};
    private static int start_index = -1;
    private static final int ADJACENT = 3;

    public static void main(String args[]){
        int sum = 0;
        int max_sum = 0;
        for(int i=0; i<(input.length-ADJACENT + 1); i++){
            if(i == 0){
                sum = input[i] + input[i+1] + input[i+2];
                max_sum = sum;
                start_index = i;
            }else{
                 sum = (sum - input[i-1] + input[i+2]);
                 if(sum > max_sum){
                     max_sum = sum;
                     start_index = i;
                 }
            }
            System.out.println("i : " + i + ", sum : " + sum);
        }
        System.out.println("sum : " + sum + ", index : " + start_index);
    }
}

Output:

run:

i : 0, sum : 20

i : 1, sum : 17

i : 2, sum : 19

i : 3, sum : 17

i : 4, sum : 21

sum : 21, index : 4

BUILD SUCCESSFUL (total time: 0 seconds)

implement 2D array dynamically in C

#include<stdio.h>

#include<stdlib.h>

main() {

int **a;

int n;

printf(“enter the size of n for nxn matrix : “);

scanf(“%d”,&n);

int input[n];

int k = 0;

printf(“enter %d numbers : “,(n*n));

for(k = 0; k < (n*n); k ++){

scanf(“%d”,&input[k]);

}

a = malloc(sizeof(int *) * n);

int i = 0;

for(i = 0; i < n ; i ++ ){

a[i] = malloc(sizeof(int *) * n);

}

int j = 0;

int num = 0;

printf(“\nArray\n\n”);

for(i = 0; i < n; i ++ ) {

for(j = 0; j < n; j ++){

a[i][j] = input[num];

num ++;

//printf(“a[%d][%d] = %d\n”, i, j, a[i][j]);

printf(“%d | “,a[i][j]);

}

printf(“\n”);

printf(“———-\n”);

}

for(i = 0; i < n; i++){

free(a[i]);

}

free(a);

}

output :

enter the size of n for nxn matrix : 3

enter 9 numbers : 1

2

3

4

5

6

7

8

9

Array

1 | 2 | 3 |

———-

4 | 5 | 6 |

———-

7 | 8 | 9 |

———-

remove duplicates from list of integers – C

#include<stdlib.h>

struct node {

int data;

struct node* next;

};

int doHash(int);

void fixInHash(int, struct node**);

void printHash(struct node**);

main(){

int a[] = {2,1,2,3,4,5,4,3,5};

//int a[] = {8,2,9,3,1,4,5,12,4,3,12,15};

int len = sizeof(a)/sizeof(a[0]);

printf(“len : %d\n”,len);

struct node* hashMap[len];

int i = 0;

printf(“Input array : “);

for( i = 0; i < len; i ++ ){

printf(“%d “, a[i]);

}

printf(“\n”);

for( i = 0; i < len; i ++){

hashMap[i] = NULL;

}

for( i = 0; i < len; i ++){

int index = doHash(a[i]);

fixInHash(a[i],&(hashMap[index]));

}

printf(“After removing duplicates : “);

for(i = 0; i < len; i ++ ){

printHash(&hashMap[i]);

}

printf(“\n”);

}

void printHash(struct node** elem){

while((*elem) != NULL){

printf(” %d “,(*elem)->data);

(*elem) = (*elem)->next;

}

}

int doHash(int num){

int a = 1;

int b = 2;

int n = 5;

int ret = 0;

/* we will use hash function as h(x) = (ax + b)mod n */

ret = (a * num + b) % n;

return ret;

}

void fixInHash(int value, struct node** elem) {

struct node* current = NULL;

current = (struct node*) malloc(sizeof(struct node));

int flag = 0;

//printf(“value : %d\n”,value);

if( *elem == NULL){

current->data = value;

current->next = *elem;

*elem = current;

//printf(“null : %d\n”,(*elem)->data);

} else {

//printf(“inside else : %d \n”, (*elem)->data);

while((*elem) != NULL ){

if((*elem)->data == value){

//printf(“match : %d\n”,(*elem)->data);

flag = 1;

break;

}

if((*elem)->next != NULL) {

(*elem) = (*elem)->next;

}else{

break;

}

}

if(flag == 0){

current->data = value;

current->next = *elem;

*elem = current;

//printf(“inside flag : %d\n”,(*elem)->data);

}

}

}

Output :

Input array : 2 1 2 3 4 5 4 3 5

After removing duplicates :  3  4  5  1  2

binary search – c

#include<stdio.h>

#include<stdlib.h>

void doBinarySearch(int [], int , int , int );

main() {

//int a[] = { 0,1,2,3,4,5,6,7,8,9,10 };

int a[] = { 1,2,3,4,5,8,9 };

int num;

int length = sizeof(a)/sizeof(a[0]);

printf(“Enter the number from 0 – 10 : “);

scanf(“%d”,&num);

doBinarySearch(a, 0, length -1, num);

}

void doBinarySearch(int a[], int start, int len, int num) {

if(start > len) {

//printf(“start : %d and len : %d\n”,start,len);

printf(“Number not found\n”);

exit(-2);

}

int mid = (start + len) / 2;

if(num == a[start]){

printf(“start – found at index : %d\n”,start);

exit(0);

}

if(num == a[len]){

printf(“end – found at index : %d\n”,len);

exit(0);

}

if(num == a[mid]){

printf(“mid – found at index : %d\n”,mid);

exit(0);

}

if(num < a[mid]){

//printf(“less: %d – %d\n”, start, (mid-1));

doBinarySearch(a, start, (mid -1), num);

}

if(num > a[mid]){

//printf(“greater : %d – %d\n”, (mid+1),len);

doBinarySearch(a, (mid + 1), len, num);

}

}

sort array of 0s and 1s

#include<stdio.h>

void sort(int [],int);

main(){

int a[] = {0,1,0,0,1,1,1,1,0,0,1,0};

int length = sizeof(a)/sizeof(a[0]);

sort(a,length-1);

}

void sort(int a[],int j){

int i = 0;  int n = j;

while( i < j ) {

while(a[i] == 0 && i < j){

i ++;

}

while(a[j] == 1 && j > i){

j –;

}

if( i < j ){

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

for(i = 0; i < n; i ++){

printf(“%d “,a[i]);

}

printf(“\n”);

}

This is O(N) solution

Finding duplicate value in unsorted array in linear time

This was an interesting problem given to me by Dada since I am new to puzzles and algos. I am sure you would like this.

Problem

Given an unsorted array A[1...n]. There is one duplicate number in the array which you need to find out.

Solution

We already know that there are n element and there is only one duplicate number.

Lets solve this, we will take the n = 8, means there are 8 elements in array with range of 1…8. Now since there is one duplicate number the actual range of numbers will be 1….[n-1] i.e. 1..7

I assume here that many people would be aware of XOR operators, so we are going to use XOR operators to find the duplicate numbers. But just to take a quick re-cap XOR has the following property

p	q	p + q
0	0	0
0	1	1
1	0	1
1	1	0

What next we will do that we will calculate the XOR of the range 1…[n-1] which is 1…7 here. Lets call the result as XOR(range). Now the next thing is to calculate the XOR if the range calculated just now i.e. XOR(range) with the array elements given in the problem. Why we are doing this is because when we will caculate this the number with even occurences will go out and the the only element remaining will be the duplicate which we have to find out. Lets’ check the program now.

Program

package com.bundle.algos;

//In this kind of problems you know the range of the elements
// in this example range is 1-7 and total number of elements is 8
public class FindDuplicateInArray {
static int xorArray,dup;
public static void main(String args[]){
int[] _array = new int[]{1,2,6,3,4,5,6,7};
//int[] _array = new int[]{11,12,13,14,14,15,16};
int duplicate = findWithXOR(_array);
System.out.println(“Duplicate : ” + duplicate);
}
public static int findWithXOR(int[] input){
int xorArray=1;//,dup=0;
for(int i=2; i<=(input.length-1);i++){
xorArray = xorArray ^  i;
//System.out.println(“XOR : ” + xorArray);
}
System.out.println(“XOR Array : ” + xorArray);
for(int k=0;k<=input.length-1;k++){
xorArray = xorArray ^ input[k];
System.out.println(xorArray);
}
//System.out.println(“Duplicate : ” + dup);
return xorArray;
}
}

Complexity of the problem

This will be θ(n)  which is the best part of the solution.

This solution is for a known range of 1..n. I will come up with some more generic solutions soon.