CC-18 : Find next bad version number.

Description:

Assume that a software releases version in series such as 1,2,3,4,5,6,7..If a bug is introduced in release 2 and moves undetected in next releases, then the next bad version after release 2 is release 3. Given a series of releases and the first bad version release number, we need to find the next bad version number.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 1, 2, 3, 4, 5, 6, 7,	Next bad num after 4 is 5 Next bad num after 7 is none Next bad num after 1 is 2

Pseudocode:

SearchNextBadNumber class:

Initialize integer member variable named badNum to 0.

setBadNum (num):

Set badNum member variable to num.

isBadNum (num):

If num > badNum return true else return false.

nextBadNum(nums[]):

Integer array named nums is received as input parameter.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.

While (firstIdx <= lastIdx) do the following steps:

Set integer variable midIdx to (lastIdx+firstIdx)/2.

If (isBadNum(midIdx) == true) && (isBadNum(midIdx-1)== false):

Return midIdx as we have found the next bad version.

Else if isBadNum[midIdx-1] == true then:

Set lastIdx=(midIdx-1).

Else:

Set firstIdx=midIdx+1.

Return -1 as we could not find a higher bad version.

Code:

public class SearchNextBadNumber {

private int badNum=0;

public void setBadNum(int badNum) {
	this.badNum=badNum;
}

public boolean isBadNum(int num) {
	if (num >= badNum) {return true; }
	else {
		return false;
	}	
}


public int nextBadNum(int[] nums){
	if (nums.length<=1) {return 0;}
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if ((isBadNum(midIdx)==true)&&(! isBadNum(midIdx-1)==true)) {
			return midIdx;
		} else { if (isBadNum(midIdx-1) == true) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return -1;
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchNextBadNumber {

private int badNum=0;

public void setBadNum(int badNum) {
	this.badNum=badNum;
}

public boolean isBadNum(int num) {
	if (num >= badNum) {return true; }
	else {
		return false;
	}	
}


public int nextBadNum(int[] nums){
	if (nums.length<=1) {return 0;}
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if ((isBadNum(midIdx)==true)&&(! isBadNum(midIdx-1)==true)) {
			return midIdx;
		} else { if (isBadNum(midIdx-1) == true) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return -1;
}



public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchNextBadNumber search=new SearchNextBadNumber();
	int[] nums= { 1,2,3,4,5,6,7};
		
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	int badNum=4;
	search.setBadNum(badNum);
	retVal=search.nextBadNum(nums);
	if (retVal != -1) {
	System.out.println("\n\n"+" Next bad num after "+ badNum + " is  "+ nums[retVal]);
	}else {
		System.out.println("\n\n"+" Next bad num after "+ badNum + " is  *none*");
	}
	
	badNum=7;
	search.setBadNum(badNum);
	retVal=search.nextBadNum(nums);
	if (retVal != -1) {
		System.out.println("\n\n"+" Next bad num after "+ badNum + " is  "+ nums[retVal]);
		}else {
			System.out.println("\n\n"+" Next bad num after "+ badNum + " is  *none*");
	}
	
	
	badNum=1;
	search.setBadNum(badNum);
	retVal=search.nextBadNum(nums);
	if (retVal != -1) {
		System.out.println("\n\n"+" Next bad num after "+ badNum + " is  "+ nums[retVal]);
		}else {
			System.out.println("\n\n"+" Next bad num after "+ badNum + " is  *none*");
	}
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}