Amit Kumar Yadav
BAN USERI started with 2 sub-Arrays. Front-Array starts with only one element and grows till the 2nd last element ((n-1)st element). The Back array consists all the elements from 2nd element to the last element (nth element) and it reduces to just one element(last element).
Loop Invariant:
The sum of the size of sub-arrays = size of the input array
The total elements' sum of sub-arrays = elements' sum of the input array
public static int findBreakPoint(int[] array)
{
int sumFrontArray = array[0], sumBackArray = 0;
for(int i = 1 ; i < array.length ; i++)
sumBackArray += array[i];
if(sumFrontArray == sumBackArray)
return 0; // returning 0th index
for(int i = 1 ; i < array.length - 1 ; i++)
{
sumFrontArray += array[i];
sumBackArray -= array[i];
if(sumFrontArray == sumBackArray)
return i; // return the index when found
}
return -1; // return -1 when breaking point not found
}
@-thelineofcode: Thank you very much. I have corrected the code. It is working now. There was major flaw in logic which I didn't pay attention to. Thanks again.
- Amit Kumar Yadav January 18, 2014Can you please put some more light on what do you mean by reversing a matrix here ? Is it row-wise reversal or column-wise ? I apologize if this is intuitive and I am unable to figure it out.
- Amit Kumar Yadav January 17, 2014public static String addUsingString(String firstNumber, String secondNumber)
{
if(firstNumber == null && secondNumber != null)
return secondNumber;
if(secondNumber == null && firstNumber != null)
return firstNumber;
int carry = 0;
String result = "";
for(int i = firstNumber.length() - 1, j = secondNumber.length() - 1 ; i >= 0 || j >= 0 ; i--, j--)
{
if(i < 0)
{
while(j >= 0)
{
int valTwo = (int)secondNumber.charAt(j)- (int)'0';
int sum = carry + valTwo;
carry = 0; // reseting carry for next iteration
if(sum > 9)
{
carry = sum / 10;
sum = sum % 10;
}
result = sum + result;
j--;
}
if(carry != 0)
result = carry + result;
return result;
}
else if(j < 0)
{
while(i >= 0)
{
int valOne = (int)firstNumber.charAt(i)- (int)'0';
int sum = carry + valOne;
carry = 0; // reseting carry for next iteration
if(sum > 9)
{
carry = sum / 10;
sum = sum % 10;
}
result = sum + result;
i--;
}
if(carry != 0)
result = carry + result;
return result;
}
else
{
int valOne = (int)firstNumber.charAt(i) - (int)'0';
int valTwo = (int)secondNumber.charAt(j) - (int)'0';
int sum = carry + valOne + valTwo;
carry = 0; // reseting carry for next iteration
if(sum > 9)
{
carry = sum / 10;
sum = sum % 10;
}
result = sum + result;
}
}
if(carry != 0)
result = carry + result;
return result;
}
The solution I am providing is the solution to find the connected components using DFS in an UnDirected Graph. Here each employee is considered as a Node and the other employees he/she works with are the adjacentNodes. The code gives correct solution to me. Please try and let me know if it fails on some conditions..
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class EmployeeEmployeeRelation
{
private static boolean[] marked; // to check is a node(employee) is visited
private static int[] groupNumber; // groupNumber of the node(employee)
private static int count = 1; // count assigns the groupNumber
public static void findGroups(String[] employeeInformation)
{
int totalEmployees = employeeInformation.length;
marked = new boolean[totalEmployees];
groupNumber = new int[totalEmployees];
for(int i = 0 ; i < totalEmployees ; i++)
{
if(!marked[i])
{
findAdjacentEmployees(employeeInformation, employeeInformation[i], i); // calling DFS
count++;
}
}
// Mapping each employee to its group
Map<Integer, List<String>> employeeGroups = new HashMap<Integer, List<String>>();
for(int i = 0 ; i < totalEmployees ; i++)
{
List<String> group = employeeGroups.get(groupNumber[i]);
if(group == null)
employeeGroups.put(groupNumber[i], group = new ArrayList<String>());
group.add(employeeInformation[i]);
}
//Printing the group
for(Map.Entry<Integer, List<String>> m : employeeGroups.entrySet())
System.out.println(m.getKey() + " : " + m.getValue());
}
// Applying DFS sort of technique to find the adjacent nodes. The method is nothing but DFS.
public static void findAdjacentEmployees(String[] employeeInformation, String currentEmployee, int id)
{
marked[id] = true;
groupNumber[id] = count;
char[] empId = currentEmployee.toCharArray();
for(int i = 0 ; i < empId.length ; i++)
if(empId[i] == '1')
if(!marked[i])
findAdjacentEmployees(employeeInformation, employeeInformation[i], i);
}
public static void main(String[] args)
{
String[] inputArray = {"0110000", "1010000", "1100000", "0000001", "0001000", "0000100", "0000010"};
findGroups(inputArray);
}
}
public static boolean isPresentInArray_K(int number, int k)
{
//base conditions
if(k == 1)
return true;
if(k >= 2 && (number % 2) == 0)
return false;
// approach for the Array3 and after
else
{
int positionInArrayTwo = (int) Math.ceil((double)number/2);
System.out.println("The position of " + number + " in Array_2 is : " + positionInArrayTwo);
int positionInPreviousArray = positionInArrayTwo;
int positionInCurrentArray;
for(int i = 3 ; i <= k ; i++)
{
if(positionInPreviousArray % i == 0)
return false;
positionInCurrentArray = positionInPreviousArray - (positionInPreviousArray / i);
System.out.println("The position of " + number + " in Array_" + i + " is : " + positionInCurrentArray);
positionInPreviousArray = positionInCurrentArray;
}
return true;
}
- Amit Kumar Yadav January 04, 2014
- Amit Kumar Yadav November 13, 2014