Finding the missing number in a sequential array with minimum complexity

Finding the missing number using binary search

Description :


/**
 * Find missing number in a sequence Minimum complexity (n Log n)
 *
 * input : {1,2,3,5}
 * output : 4
 */
package com.steffi.solutions;

import java.util.Arrays;

/**
 * @author Consumerfed Information Technology Section
 *
 */
public class MissingNumberArray {

private static int loopCount = 0;

public static void main(String[] args) {
long startTime = System.currentTimeMillis();
int[] a = {1,2,3,4,6,7,8,9,10,11,12};
int len = a.length;
MissingNumberArray m = new MissingNumberArray();
int value = 0;
if(a[len-1]!=len) {
value = m.findMissingNumber(a, 0, len);
System.out.println(" The Missing number in the array :"+Arrays.toString(a)+" is "+value);
}else {
loopCount++;
System.out.println(" There is no missing number in the given array "+Arrays.toString(a));
}
System.out.println(" For "+len+" size array it tooks "+loopCount+" search to find the answer ");
System.out.println(" Complexity :"+len*Math.log(len));
System.out.println(" Time Taken : "+(System.currentTimeMillis() - startTime)+" ms");

}

private int findMissingNumber(int[] array, int startPstn, int endPstn) {
loopCount++;
int arraySize = endPstn - startPstn;
int position = startPstn + arraySize / 2;
if(arraySize==0) {
return position +1;
}else if (arraySize == 1) {
return array[position] + 1;
}
else if (array[position] != position + 1) {
return findMissingNumber(array, startPstn, position);
} else {
return findMissingNumber(array, position + 1, endPstn);

}
}
}

Output

 The Missing number in the array :[1, 2, 3, 5] is 4
 For 4 size array it tooks 2 search to find the answer
 Complexity :5.545177444479562
 Time Taken : 4 ms

 The Missing number in the array :[1, 2, 3, 5, 6, 7, 8, 9, 10] is 4
 For 9 size array it tooks 3 search to find the answer
 Complexity :19.775021196025975
 Time Taken : 4 ms

 The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 10] is 9
 For 9 size array it tooks 3 search to find the answer
 Complexity :19.775021196025975
 Time Taken : 3 ms

 The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 9, 11] is 10
 For 10 size array it tooks 3 search to find the answer
 Complexity :23.02585092994046
 Time Taken : 2 ms

 The Missing number in the array :[1, 2, 4, 5] is 3
 For 4 size array it tooks 3 search to find the answer
 Complexity :5.545177444479562
 Time Taken : 3 ms

 The Missing number in the array :[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12] is 4
 For 11 size array it tooks 4 search to find the answer
 Complexity :26.376848000782076
 Time Taken : 3 ms

 The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14] is 13
 For 13 size array it tooks 4 search to find the answer
 Complexity :33.34434164699998
 Time Taken : 3 ms

Buy any thing from amazon through us !!!

Find the Missing number in the sequence array with minimum complexity

Algorithms to find the missing numbers from a sequences of consecutive number array using java recursion -  a complete code

/**
 * Find missing number in a sequence Minimum complexity (n Log n)
 *
 * input : {1,2,3,5}
 * output : 4
 */
package com.codecreeks.solutions;

/**
 * @author Konzernites
 *
 */
public class MissingNumberArray {

public static void main(String[] args) {
int[] a = {1,2,3,5,6};
MissingNumberArray m = new MissingNumberArray();
int value = m.findMissingNumber(a, 0, a.length);
System.out.println(value);

}

private int findMissingNumber(int[] array, int startPstn, int EndPstn) {
int arraySize = EndPstn - startPstn;
int position = startPstn + arraySize / 2;
if (arraySize == 1) {
return array[position] - 1;
}
else if (array[position] == position + 1) {
return findMissingNumber(array, position + 1, EndPstn);
} else {
return findMissingNumber(array, startPstn, position);
}
}
}


Output

4

Squaring and Sorting an input array contains negative and positive number

Questions asked in hackerearth and codeforgeeks

/**
 * Squaring and Sorting an input array contains negative and positive number
 *
 * Complexity O(2n)
 *
 */
package com.konzerntech.kozhikode;

import java.util.Arrays;

/**
 * @author Consumerfed Information Technology Section kozhikode
 * +91 8281 8080 29
 */
public class SquareAndSort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int[] input = { -10, -8, -3, -1, 4, 6, 8 };
int len = input.length;
int[] output = new int[len];

int[] a = new int[len];
int[] b = new int[len];

int aLen = 0;
int bLen = 0;

for (int i = 0; i < len; i++) {
int value = input[i];
int square = value * value;
if (value < 0) {
a[aLen] = square;
aLen++;
} else {
b[bLen] = square;
bLen++;
}
}


int aPtr = aLen-1;
int bPtr = 0;


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

if (bPtr > (bLen - 1)) {
while (aPtr >= 0) {
output[i] = a[aPtr];
i++;
aPtr--;
}
break;
}

if (aPtr < 0) {
while (bPtr < bLen) {
output[i] = b[bPtr];
i++;
bPtr++;
}
break;
}

if (b[bPtr] < a[aPtr]) {
output[i] = b[bPtr];
bPtr++;
} else {
output[i] = a[aPtr];
aPtr--;
}

}
System.out.println("Input : "+Arrays.toString(input));
System.out.println("Output : "+Arrays.toString(output));

}

}

Output

Input : [-10, -8, -3, -1, 4, 6, 8]

Output : [1, 9, 16, 36, 64, 64, 100]

Description :

Squaring and Sorting is petty tricky problem.

The array may contains both negative as well as positive integer values, so while square the array the output may not be a sorted one.

So what we did here is we divided the input array into two based on the negative and positive values after squaring it.

Then we compare the two array n th position of one array to the zero th position of the other to find the minimum value, thus found minimum value is inserted into output array.

we used pointer to point each elements in array.

Tic Tac Toe - Two player computer game developed in java | Full source code

https://www.youtube.com/watch?v=Qot3-mBNJvQ

Developed a two player tic tac toe game in java.  The user can also play with the computer,  we developed a new algorithm that makes computers to investigate user moves and to choose the best moves to win the game. So we request the readers to watch the video showing how it works.  Our developers are working on the ui parts. We will update the source code in this website soon.  You can post your comments & queries. Please follow the blog for our update. Your feedback are valuable.

Full source code will be available in this blog soon..

Tic Tac Toe Game