masterjaso
BAN USERHi oOZz,
I never said I improved on your solution, I just actually produced a coded solution and clarified the pseudo to account for the fringe case that is not obvious until a practical implementation is attempted. As for the 3rd loop for printing, I segmented that out so that it is not part of the actual 'working code', but you are correct that it could have been accomplished during the 2nd loop.
To your last point, I did not use code to implement BigInteger (neither did you sir...), but I did include an explanation of 3 different data types to address this depending on the situation. Your suggestion that my solution is incomplete depends on whether you accept my English description as complete (if not, yours is incomplete too). As to the correctness, mine is indeed correct.
Thank you for your comment and good debate.
This was an excellent exercise for me. I implemented my solution using Java, so there is no operand overloading. I have included the main section to display an example of usage.
Note: there are 3 private helper functions: gcd(Greatest Common Divisor), lcm(Least Common Multiple), reduce(to ensure the fraction is reduced after each calculation).
package fraction;
public class Fraction {
public int num;
public int den;
public Fraction(){
}
public Fraction(int n, int d){
num = n;
den = d;
}
public Fraction addition(Fraction f1){
Fraction result;
int d = lcm(den, f1.den);
int n = (num * d / den) + (f1.num * d / f1.den);
result = new Fraction(n, d);
return reduce(result);
}
public Fraction subtraction(Fraction f1){
Fraction result;
int d = lcm(den, f1.den);
int n = (num * d / den) - (f1.num * d / f1.den);
result = new Fraction(n, d);
return reduce(result);
}
public Fraction multiplication(Fraction f1){
Fraction result;
int d = den * f1.den;
int n = num * f1.num;
result = new Fraction(n,d);
return reduce(result);
}
public Fraction division(Fraction f1){
Fraction result;
int n = den * f1.num;
int d = num * f1.den;
result = new Fraction(n,d);
return reduce(result);
}
public void display(){
System.out.println(num + "/" + den);
}
public boolean isEqual(Fraction f1){
int d = lcm(den, f1.den);
int n1 = num * d / den;
int n2 = f1.num * d / f1.den;
return n1 == n2;
}
public boolean lessThan(Fraction f1){
int d = lcm(den, f1.den);
int n1 = num * d / den;
int n2 = f1.num * d / f1.den;
return n1 < n2;
}
public boolean greaterThan(Fraction f1){
int d = lcm(den, f1.den);
int n1 = num * d / den;
int n2 = f1.num * d / f1.den;
return n1 > n2;
}
private int gcd(int a, int b){
int temp;
while(b > 0){
temp = b;
b = a % b;
a = temp;
}
return a;
}
private int lcm(int a, int b){
return (a*b) / gcd(a,b);
}
private Fraction reduce(Fraction f){
int least = gcd(f.num, f.den);
if(least <= 1){
return f;
}
else{
f.num /= least;
f.den /= least;
reduce(f);
}
return f;
}
//test section - main
public static void main(String[] args) {
Fraction f = new Fraction(5, 8);
Fraction g = new Fraction(7, 16);
Fraction result;
result = f.addition(g);
result.display();
result = f.subtraction(g);
result.display();
result = f.division(g);
result.display();
result = f.multiplication(g);
result.display();
if(f.isEqual(f)) System.out.println("equal");
if(f.isEqual(g)) System.out.println("equal");
if(g.lessThan(f)) System.out.println("less");
if(f.lessThan(g)) System.out.println("less");
if(f.greaterThan(g)) System.out.println("greater");
if(g.greaterThan(f)) System.out.println("greater");
}
}
So I am assuming this is simply how to make the pixels change color and there is no end goal (like turn the screen from black to white and count the number of clicks).
1. Initialize 2D array with 0's to represent color 1.
2. Initialize mouse event handler that returns point x,y on mouse click
3. Return x,y to the colorChange function
4. colorChange then flips pixels: (x,y) (x-1,y) (x+1,y) (x,y-1) (x,y+1) to the opposite value (0's to 1's, and 1's back to 0's) as long as their current value matches the value at x,y.
4a. You must utilize edge/corner checking to make sure you do not encounter ArrayOutOfBounds Exceptions.
Approach 3 will not work for primitive types, thus you can use method 1 or 2. #1 is the preferred method in my opinion.
To pull a value out of a void*, you are required to know what is going to come out as it is being used, thus the danger or utilizing it.
To pop from method 1, you would use value = boost::any_cast<T>(list) to return a value from the desired container.
Fairly simple question. Previous poster gave the psuedo:
@oOZz
1. First pass calculate the product P of all the numbers in array A
2. Second pass recreate the array A[i] = P / A[i]
NOTE: that you do have to make a special adjustment for the first element. You set your accumulator equal to the beginning element, and then loop starting with the 2nd element. Proper pseudo would read:
1. Set accumulator variable equal to first element in the array
2. Start with 2nd element in array and accumulate the product to the end of the array
3. Start at beginning of the array and assign to each element: accumulator/element value to the end of the array
Final consideration: As the numbers get larger, you would need to implement BigInteger or use long, or possibly another customer data type to capture the massive values that can accumulate. This algorithm runs on O(n) time and O(n) space complexity.
Here is a simple implementation of the actual code.
int[] a = {5,4,8,6,2,5,1,3,9,11};
int product = a[0];
for(int i = 1; i < a.length; i++){
product *= a[i];
}
for(int i = 0; i < a.length; i++){
a[i] = product/a[i];
}
for(int i = 0; i < a.length; i++){
System.out.print(a[i] + " ");
}
Output of above example:
570240 712800 356400 475200 1425600 570240 2851200 950400 316800 259200
There are three ways to address this that I know of:
1. boost::any (and the subsequent API that goes with it)
2. void* (that can point to any type of object)
3. Create a generic base class that all of your different types inherit from, then you can create lists and arrays of the parent type for any of the children.
Be mindful with void* as it is not as type-safe as using boost::any.
The drawback to the parent class is that it can overlap and violate the paradigm of modular programming if the items are from items of vastly different types and hierarchies.
You will need to search for the boost api to get all of the details.
This was a great (and tricky) question. I challenged myself to implement a single pointer traversal, instead of using a leading/trailing pointer. The running time of this algorithm should be O(n) as it simply scans each element and copies to the new array. In the worst case it would scan and copy each element once if this was a sorted (ascending) array of integers.
This problem also required that I make special consideration for the last element in the array, should it be part of the largest ascending sequence, thus the use of the ternary operators evaluating on i==a.length.
Assumption: Duplicates are not considered "increasing", so they are not counted as such and cause the 'count' to start over.
I also incorporated Java's ArrayList class so that I could account for increasing sequences that have the same length, and subsequently print all of them.
I hope this proves helpful =)
NOTE: I use a file with 100,000 randomly generated integers to test, that is the reason for the scanner at the start to load my test case.
Scanner scanner = new Scanner(new File("IntegerArray.txt"));
int [] a = new int [100000];
int k = 0;
while(scanner.hasNextInt()){
a[k++] = scanner.nextInt();
}
ArrayList<int[]> resultSet = new ArrayList<>();
int[] result = new int[1];
int i, j;
int count = 1; //first element in sequence always counted
for(i=1; i < a.length; i++){
if(a[i-1] < a[i]){
count++; //increase the current count when increasing element found
}
else
if(count >= result.length && (a[i-1] >= a[i] || i == a.length -1) ){
if(count > result.length){resultSet.clear();}
result = new int[count];
for(j = 0; j < result.length; j++){
result[j] = (i == a.length-1) ? a[i-count+j+1] : a[i - count + j];
//edge case (End) - to make sure we capture the last element
//if it is part of the largest increasing sequence
}
count = 1;
resultSet.add(result);
}
else{count = 1;}
}
for(i=0; i < resultSet.size(); i++){
int[] temp = resultSet.get(i);
for(int x = 0; x < temp.length; x++){
System.out.println(temp[x] + " ");
}
System.out.println();
}
Be mindful of negative numbers. Your recursive solution is elegant, compact, and I like it. However, you need to turn your offset to an absolute value so that negative numbers don't throw you backwards.
- masterjaso June 05, 2013Great question here. So to avoid linear search, you simply employ the absolute value of the difference between your current element, and your guess. This will put you at the earliest position that could hold the desired value. If you find your position is outside of the array length, then the element cannot possibly exist inside of the given list. Here is my solution:
public static int operation(int[] a, int guess){
int position = 0;
int diff = 0;
while(a[position] != guess){
diff = guess - a[position];
if(diff < 0){diff *= -1;} //absolute value
position += diff;
if(position >= a.length){return -1;} //error value not in list
}
return position;
}
RepI am a good learner
Repharrylseay, Aghori Mahakal Tantrik at ASAPInfosystemsPvtLtd
I am Harry and I live in the USA but basically I am from Bangor. I live my life very ...
Repjesselblagg9, Cloud Support Associate at 247quickbookshelp
Hello, I am Jesse and I live in Springfield, USA. I am working in a company as an engineering technician ...
So for recursive algorithms (such as the binary search) you could implement the Master Method (Master Theorem).
- masterjaso July 10, 2013T(n) = aT(n/b) + O(n^d)
The important items in this theorem state that the constants a, b, and d will help determine the 3 types of running time magnitude.
Case 1: a = b^d runtime: O(n^d log n) *logarithmic*
Case 2: a < b^d runtime: O(n^d) *quadratic*
Case 3: a > b^d runtime: O(n^log-b-a) (that is log b of a) *linearithmic*
Constant 'a' is the number of recursive calls in the function. For binary search there is a single recursive call, so this is a 1.
Constant 'b' is the rate at which the recursive call reduces the main problem into sub-problems. In binary search, it splits the array in half, so this would be a 2.
Constant 'd' is the running time of the base case of the recursive function. For binary search this is 0, as the base case is simply a single index check.
So for the specific case of binary search, you can see 1 = 2^0 which is 1=1. This puts us in use case 1. That means binary search runs in O(n^0 log n) which is simplified to O(log n).
Note that the master theorem only works for recursive functions. You can see the profound impact of performance improvements when analyzing the efficiency of algorithms such as 'Strassen's Matrix Multiplication Algorithm' (O(n^2.81)) vs. the standard matrix multiplication algorithm (O(n^3)) method. The gains of getting sub-cubic are substantial, particularly in matrix intensive applications.