JavaProblems.com - Free coding problems and exercises

Showing posts with label Array. Show all posts

Binary search an array method in java

Problem:

Write a the typical and most known method that performs a binary search on the array.

Output:

Not applicable.

Solution:

public static int binarySearch(int[] a, int target) {
int min = 0;
int max = a.length - 1;
while (min <= max) {
int mid = (min + max) / 2;
if (a[mid] < target) {
min = mid + 1;
} else if (a[mid] > target) {
max = mid - 1;
} else {
return mid; // target found
}
}
return -(min + 1); // target not found
}

Problem:

Writing a binary search method for an array in java.

Output:

Not applicable.

Solution:

// Returns the index of an occurrence of the given value in
// the given array, or a negative number if not found.
// Precondition: elements of a are in sorted order
public static int binarySearch(int[] a, int target) {
return binarySearch(a, target, 0, a.length - 1);
}
// Recursive helper to implement search behavior.
private static int binarySearch(int[] a, int target,
int min, int max) {
if (min > max) {
return -1; // target not found
} else {
int mid = (min + max) / 2;
if (a[mid] < target) { // too small; go right
return binarySearch(a, target, mid + 1, max);
} else if (a[mid] > target) { // too large; go left
return binarySearch(a, target, min, mid - 1);
} else {
return mid; // target found; a[mid] == target
}
}
}

Problem:

Write a methoe that binary search an array using Comparable in Java.

Output:

Not applicable.

Solution:

public static int binarysearch(Comparable[] items, Comparable target, int first, int last)
  {
    if(first>last)
      return -1;
    else
    {
      int middle=(first+last)/2;
      int value=target.compareTo(items[middle]);
      if(value==0)
        return middle;
      else if(value>0)
        return binarysearch( items,  target,  middle+1,  last);
      else
        return binarysearch( items,  target,  first ,  middle-1);

    }

Problem:

Write a java program that uses binary search to search array
using Comparable in Java

Output:

Not applicable.

Solution:

public class Linearsearch
{
  public static void main(String[] args)
  {
    String[] stuff={"a","b","c"};
    System.out.println(linearsearch(stuff,"b", 0));
    System.out.println(binarysearch(stuff,"a", 0, stuff.length-1));
  }
  public static int linearsearch(Comparable[] items, Comparable target, int posfirst)
  {
    if(posfirst==items.length)
      return -1;
    else if(items[posfirst].compareTo(target)==0)
    {
      return posfirst;
    }
    else
      return linearsearch(items, target,  (posfirst+1));
  }

Problem:

Write an method that sorts an array using recursion in Java

Output:

Not applicable.

Solution:

public static void sort(double[] list) {
  sort(list, list.length - 1);
  }
 
  public static void sort(double[] list, int high) {
  if (high > 1) {
  // Find the largest number and its index
  int indexOfMax = 0;
  double max = list[0];
 for (int i = 1; i <= high; i++) {
 if (list[i] > max) {
 max = list[i];
 indexOfMax = i;
 }
 }
 // Swap the largest with the last number in the list
 list[indexOfMax] = list[high];
 list[high] = max;
 // Sort the remaining list
 sort(list, high - 1);
 }

Problem:

Write a program called FindValue. The program creates an array of 20 integers, and initializes this array to some values. The program will then ask the user to enter three integer values and searches the array for the first of any of these values. Once one of the values is found, the program will display which value of the three is found first and the location where it was found. No further searches are performed. If however none of the three values was found, then the program must indicate that to the user.

Once done, calculate the complexity (Big O) of your program.

For example if the array is as follows (Notice that this is just an example; your solution must NOT refer to this example in anyways):

and the user enters 10, 25 and 80 then the output should look like the following:

One of the three values, 80, was found first. It was found at index #4.

On the other hand, if the user enters 88, 16 and 36 then the output will be as follows:

None of the three values was found in the array.

The initial part of the solution is given below to assist you.

Import java.util.Scanner;

Public class FindValue{

Public static void main(String[] args) {

int v1, v2, v3, i; //Read the three values and put them in v1, v2 and v3

…….

}//end of main

} //end of class FindValue

Solution:

import java.util.Scanner;

public class FindValue
{
 public static void main (String[] args)
 {
  int v1, v2, v3, i; //Read the three values and put them in v1, v2 and v3
  Scanner scan = new Scanner(System.in);
  int index=0, value=0;
  int[] nums = new int[20];
  v1 =scan.nextInt();
  v2 =scan.nextInt();
  v3 =scan.nextInt();

  for (i= 0; i < nums.length;i++)
   nums[i] = (int)(Math.random()*20 + 1);
  for (i = 0; i < nums.length;i++)
  {
   if (v1 == nums[i])
   {
    index = i;
    value = nums[i];
    break;
   }
   
   else if (v2 == nums[i])
   {
    index = i;
    value = nums[i];
    break;
   }
   
   else if (v2 == nums[i])
   {
    index = i;
    value = nums[i];
    break;
   }
  }
  
  if (value == 0)
   System.out.println("None of the three " +
     "values was found in the array.");
  
  else
   System.out.println("One of the three values, " + value + " was found first." +
     " It was found at index #" + index + ".");
  /**
   *The complexity is O(n).
   */
 }//end of main
} //end of class FindValue

Problem:

Assume that each month consists of 30 days. One year, then, consists of 30×12 = 360 days, i.e., there are 360 different possible birthdays. Write three programs named Problem3a.java, Problem3b.java and Problem3c.java to answer the questions below. Each of your programs should simulate choosing people at random and checking their birthdays.

a. In Problem3a.java, generate 100 birthdays at random (a number from 0 to 359), and store them in an array of size 100. The program asks the user to enter the current date (day [any number between 1 and 30] and month [any number between 1 and 12]) and determines whether any of the people have their birthday today (i.e. on the entered date). If so, display a Happy Birthday message to the found person; otherwise display the message “No one has his birthday today”. Example: if person 14 was found to have his birthday on the date entered by the user, the program displays the message: Happy Birthday to P14!

b. In Problem3b.java, you have to find how many random people you have to select before you find three people who share the same birthday? To answer this question, you have to generate birthdays at random (a number from 0 to 359) and keep track of how many people have been found with each birthday. An algorithm for this program is shown below:

Let count = 0 //count the number of people/birthdays generated

Repeat:

Select a birthday at random

Add one to count

Add one to the number of times that birthday has been found

If this is the third time that birthday has occurred:

break out of the loop

Output the count

c. In Problem3c.java, you have to find out how many different people you have to check before you find at least one person with a birthday on each of the 360 days of the year?

Output:

Not needed.

Solution:

/** ----------------------------Problem3a--------------------------- */
import java.util.*;
import java.math.*;
import java.util.Random;
public class Problem3a 
{
 public static void main(String args[])
 {
  int a[] = new int[100];
  int found = -1;
  
  Random ran = new Random();
  Scanner scan = new Scanner(System.in);
  
  for(int i = 0; i < 100; i++)
  {
   a[i] = ran.nextInt(360);
   //System.out.println(a[i]); 
//If you want to print the array of the random numbers generated
  }
  
  System.out.println("Enter day:");
  int day = scan.nextInt();
  System.out.println("Enter month:");
  int month = scan.nextInt();
  
  int val = 30 * (month - 1) + (day - 1);
  
  for(int i = 0; i < 100; i++)
  {
   if(a[i] == val)
   {
    found = i;
    break;
   }
  }
  
  if(found == -1)
  {
   System.out.println("No one has his birthday today");
  }
  else
  {
   System.out.println("Happy birthday P" + found);
  }
 }
    
}
/** ----------------------------Problem3b--------------------------- */
import java.util.*;
import java.math.*;
import java.util.Random;


public class Problem3b 
{
 public static void main(String args[])
 {
  int a[] = new int[360];
  int count = 0;
  Random ran = new Random();
  
  for(;;)
  {
   int r = ran.nextInt(360);
   count++;
   a[r]++;
   if(a[r] >= 3)
   {
    break;
   }
  }
  
  System.out.println("The count is: " + count);
 }  
}

/** ----------------------------Problem3c--------------------------- */
import java.util.*;
import java.math.*;
import java.util.Random;


public class Problem3c 
{
 public static void main(String args[])
 {
  int a[] = new int[360];
  int count = 0;
  Random ran = new Random();
  int done = 0;
  
  for(;;)
  {
   int r = ran.nextInt(360);
   count++;
   
   if(a[r] == 0)
    done++;
    
   a[r]++;
   
   if(done == 360)
    break; 
  }
  
  System.out.println("The count is: " + count);
 }  
}

Problem:

Fibonacci series are a type of series such that the value of an element is the sum of the 2 previous values for example 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… it should always start with a 0 and 2 as the first 2 elements. Write a program that takes from the user a value N then display the elements of the series up to the nth element and print them.
Fibonacci: f(n) = f(n-1) + f(n-2)

Output:

Not needed.

Solution:

import java.util.Scanner;
public class Fibonacci {


public static void main(String[] args) {


Scanner sc = new Scanner(System.in);

System.out.print("How many fib terms would you like to display? ");
int length = sc.nextInt();
int[] p = new int[length]; //set new array p equal the defined user length
printTerms( p, length ); //method to print terms
}


//method to populate and calculate array and fib sequence

public static int getNTerms( int[] p, int length ) {

//print first two terms
p[1] = 0;
p[2] = 1;
int newTerm = 0; //new value to calculate new terms on the sequence other that the first two
if ( length == 1 )
System.out.println(p[1]);
else if ( length == 2 )
System.out.println( p[1] + " " + p[2]);
else { //print rest of terms
System.out.print( p[1] + " " + p[2] + " ");
//for loop to calculate the rest of the terms
for ( int index = 3; index <= length; index++) {
newTerm = p[1] + p[2];
System.out.print( newTerm + " ");
p[1] = p[2];
p[2] = newTerm;
}
}
return newTerm;
}

public static void printTerms ( int[] p, int lenght ) {

System.out.print(getNTerms ( p, lenght ));
}
}

Problem:

Write a program that helps visualize grade distribution in your class. To do so, your program should first ask the user the number of grades he wishes to enter. Then for every entered grade you should count the number As (90 to 100), Bs (80 to 99), Cs (70 to 89), Ds (60 to 69) and Fs (below 60) (using a switch statement). Next, you will print a bar chart of stars where for each letter the number of stars corresponds to the number of grades in that range.

Output:

Please enter the number of grades you wish to view:
8
Please enter the 8 grades:
91
92
81
82
71
72
61
50
The visual grade distribution is:
A:**
B:**
C:**
D:*
F:*

Solution:

import java.util.Scanner;

public class Problem3 
{
    public static void main (String args []) 
    {
     Scanner scan = new Scanner (System.in);
 int Acount = 0;
     int Bcount = 0;
     int Ccount = 0; 
     int Dcount = 0;
    int Fcount = 0;
  
     System.out.println("Please enter the number of grades you wish to view:");
     int numgrades = scan.nextInt();
     System.out.println("Please enter the " + numgrades + " grades: ");
     int i = 1; 
     while (i <= numgrades)
     {
            int grade = scan.nextInt();
            grade = grade/10;
            switch(grade)
            {
      case 10:
      case 9:
                    Acount++;
                    break;
      
      case 8:
                    Bcount++;
                    break;
      
      case 7:
                    Ccount++;
                    break;
      
                case 6:
                    Dcount++;
                    break;
      
      default:
                    Fcount++;
                    break;
      }
            i++;
     }
     
 System.out.println("The visual grade distribution is:");
        
        System.out.print("A:");
 int j = 1;
     while(j <= Acount)
        {
            System.out.print("*");
            j++;
 }
        System.out.println();
        
 System.out.print("B:");
 j = 1;
 while(j <= Bcount)
        {
            System.out.print("*");
            j++;
 }
        System.out.println();
 
 System.out.print("C:");
     j = 1;
 while(j <= Ccount)
        {
            System.out.print("*");
            j++;
 }
        System.out.println();
        
 System.out.print("D:");
        j = 1;
 while(j <= Dcount)
        {
            System.out.print("*");
            j++;
 }
        System.out.println();
        
 System.out.print("F:");
        j = 1;
 while(j <= Fcount)
        {
            System.out.print("*");
            j++;
 }
        System.out.println();
    }   
}

Problem:

Write a program that would read the class grades from the user(5 grades). Then the code will display the maximum grade, minimum grade, and average of the. Then compute the average letter grade using the conditional statement(if else) and print the class average.

Please enter the grades:
85
98
72
64
53

Then, your program should print:
Maximum: 98
Minimum: 53
Average: 74.4
The Class Average is: C+

Solution:

/**
 * @(#)Problem2.java
 *
 *
 * @author 
 * @version 1.00 2012/10/16
 */


public class Problem2 {

    public Problem2() {
  
 We don't have a solution yet! If you were able to solve it, feel free to send it to our website.
    }
}

Problem:

Start with two arrays of strings, a and b, each in alphabetical order, possibly with duplicates. Return the count of the number of strings which appear in both arrays. The best "linear" solution makes a single pass over both arrays, taking advantage of the fact that they are in alphabetical order.

commonTwo({"a", "c", "x"}, {"b", "c", "d", "x"}) → 2
commonTwo({"a", "c", "x"}, {"a", "b", "c", "x", "z"}) → 3
commonTwo({"a", "b", "c"}, {"a", "b", "c"}) → 3

Solution:

public int commonTwo(String[] a, String[] b) {   
  int count = 0;
  String str = "";
  for (int i = 0; i < b.length; i++) {
    for (int j = 0; j < a.length; j++) {
      if (a[j].equals(b[i]) && !str.contains(a[j])) {
        str += a[j];
        count++;
      }
    }
  }
  return count;
}

Problem:

Start with two arrays of strings, A and B, each with its elements in alphabetical order and without duplicates. Return a new array containing the first N elements from the two arrays. The result array should be in alphabetical order and without duplicates. A and B will both have a length which is N or more. The best "linear" solution makes a single pass over A and B, taking advantage of the fact that they are in alphabetical order, copying elements directly to the new array.

mergeTwo({"a", "c", "z"}, {"b", "f", "z"}, 3) → {"a", "b", "c"}
mergeTwo({"a", "c", "z"}, {"c", "f", "z"}, 3) → {"a", "c", "f"}
mergeTwo({"f", "g", "z"}, {"c", "f", "g"}, 3) → {"c", "f", "g"}

Solution:

public String[] mergeTwo(String[] a, String[] b, int n) {
  String out[] = new String[n];
  int aindex =0, bindex=0;
  for(int i=0; i<n; i++)
  {
    int cmp = a[aindex].compareTo( b[bindex] );
    if(cmp<=0)
    {
      out[i] = a[aindex++];
      if(cmp == 0) bindex++;
    }
    else
    {
      out[i] = b[bindex++];
    }
  } 
  return out;
}

Problem:

(A variation on the sumHeights problem.) We have an array of heights, representing the altitude along a walking trail. Given start/end indexes into the array, return the number of "big" steps for a walk starting at the start index and ending at the end index. We'll say that step is big if it is 5 or more up or down. The start end end index will both be valid indexes into the array with start <= end.

bigHeights({5, 3, 6, 7, 2}, 2, 4) → 1
bigHeights({5, 3, 6, 7, 2}, 0, 1) → 0
bigHeights({5, 3, 6, 7, 2}, 0, 4) → 1

Solution:

public int bigHeights(int[] heights, int start, int end) {
  int tmp = 0;
  for (int i = start; i <= end-1; i++) {
    if (Math.abs(heights[i] - heights[i+1]) >= 5) {
      tmp++;
    }
  }
  return tmp;
}

Problem:

This is slightly more difficult version of the famous FizzBuzz problem which is sometimes given as a first problem for job interviews. (See also: FizzBuzz Code.) Consider the series of numbers beginning at start and running up to but not including end, so for example start=1 and end=5 gives the series 1, 2, 3, 4. Return a new String[] array containing the string form of these numbers, except for multiples of 3, use "Fizz" instead of the number, for multiples of 5 use "Buzz", and for multiples of both 3 and 5 use "FizzBuzz". In Java, String.valueOf(xxx) will make the String form of an int or other type. This version is a little more complicated than the usual version since you have to allocate and index into an array instead of just printing, and we vary the start/end instead of just always doing 1..100.

fizzBuzz(1, 6) → {"1", "2", "Fizz", "4", "Buzz"}
fizzBuzz(1, 8) → {"1", "2", "Fizz", "4", "Buzz", "Fizz", "7"}
fizzBuzz(1, 11) → {"1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz"}

Solution:

public String[] fizzBuzz(int start, int end) {
    int n = end - start;
    String[] result = new String[n];
 
    int pos = 0;
    for (int i = start; i < end; i++) {
        boolean fizz = i % 3 == 0;
        boolean buzz = i % 5 == 0;
 
        if (fizz && buzz) result[pos] = "FizzBuzz";
        else if (fizz) result[pos] = "Fizz";
        else if (buzz) result[pos] = "Buzz";
        else result[pos] = String.valueOf(i);
        pos++;
    }
    return result;
}

Problem:

Return an array that contains the exact same numbers as the given array, but rearranged so that all the even numbers come before all the odd numbers. Other than that, the numbers can be in any order. You may modify and return the given array, or make a new array.

evenOdd({1, 0, 1, 0, 0, 1, 1}) → {0, 0, 0, 1, 1, 1, 1}
evenOdd({3, 3, 2}) → {2, 3, 3}
evenOdd({2, 2, 2}) → {2, 2, 2}

Solution:

public int[] evenOdd(int[] nums) {
  int countE = 0;
  int countO = nums.length-1;
  int[] array = new int[nums.length];
  
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] % 2 == 0) {
      array[countE] = nums[i];
      countE++;
    } 
    else {
      array[countO] = nums[i];
      countO--;
    }
  }
  return array;
}

Problem:

Return a version of the given array where each zero value in the array is replaced by the largest odd value to the right of the zero in the array. If there is no odd value to the right of the zero, leave the zero as a zero.

zeroMax({0, 5, 0, 3}) → {5, 5, 3, 3}
zeroMax({0, 4, 0, 3}) → {3, 4, 3, 3}
zeroMax({0, 1, 0}) → {1, 1, 0}

Solution:

public int[] zeroMax(int[] nums) {
  int max = 0;
  
  for (int i = nums.length-1; i >= 0; i--) {
    if (nums[i] % 2 != 0)
      max = Math.max(max, nums[i]);
    if (nums[i] == 0)
          nums[i] = max;
  }
  return nums;
}

Problem:

Return a version of the given array where all the 10's have been removed. The remaining elements should shift left towards the start of the array as needed, and the empty spaces a the end of the array should be 0. So {1, 10, 10, 2} yields {1, 2, 0, 0}. You may modify and return the given array or make a new array.

withoutTen({1, 10, 10, 2}) → {1, 2, 0, 0}
withoutTen({10, 2, 10}) → {2, 0, 0}
withoutTen({1, 99, 10}) → {1, 99, 0}

Solution:

public int[] withoutTen(int[] nums) {
  int[] result = new int[nums.length];
  int j = 0;
  for(int i = 0; i < nums.length; i++) {
    if(nums[i] == 10) {
    } else {
      result[j] = nums[i];
      j++;
    }
  }
  
  for(int i = j; i < nums.length; i++) {
    result[i] = 0;
  }
  return result;
}

Problem:

Return an array that contains the exact same numbers as the given array, but rearranged so that all the zeros are grouped at the start of the array. The order of the non-zero numbers does not matter. So {1, 0, 0, 1} becomes {0 ,0, 1, 1}. You may modify and return the given array or make a new array.

zeroFront({1, 0, 0, 1}) → {0, 0, 1, 1}
zeroFront({0, 1, 1, 0, 1}) → {0, 0, 1, 1, 1}
zeroFront({1, 0}) → {0, 1}

Solution:

public int[] zeroFront(int[] nums) {
  int count = 0;
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] == 0) {
      nums[i] = nums[count];
      nums[count] = 0;
      count++;
    }
  }
  return nums;
}

Problem:

We'll say that an element in an array is "alone" if there are values before and after it, and those values are different from it. Return a version of the given array where every instance of the given value which is alone is replaced by whichever value to its left or right is larger.

notAlone({1, 2, 3}, 2) → {1, 3, 3}
notAlone({1, 2, 3, 2, 5, 2}, 2) → {1, 3, 3, 5, 5, 2}
notAlone({3, 4}, 3) → {3, 4}

Solution:

public int[] notAlone(int[] nums, int val) {
  for (int i = 0; i < nums.length; i++) {
    if (i > 0 && i < nums.length-1 && nums[i] == val) {
      if (nums[i] != nums[i-1] && nums[i] != nums[i+1])
      nums[i] = Math.max(nums[i-1], nums[i+1]);
      
    }
  }
  return nums;
}

Problem:

Given a non-empty array of ints, return a new array containing the elements from the original array that come after the last 4 in the original array. The original array will contain at least one 4. Note that it is valid in java to create an array of length 0.

post4({2, 4, 1, 2}) → {1, 2}
post4({4, 1, 4, 2}) → {2}
post4({4, 4, 1, 2, 3}) → {1, 2, 3}

Solution:

public int[] post4(int[] nums) {
  for (int i = nums.length-1; i >= 0; i--) {
    if (nums[i] == 4) {
      int[] foo;
      foo = new int[nums.length-i-1];

      for (int j = 0; j < foo.length; j++) {
        foo[j] = nums[i+j+1];
      }
      return foo;
    }
  }
  
  int[] bar;
  bar = new int[0];
  return bar;
}

Subscribe to: Posts ( Atom )

Problem:

Output:

Solution:

Problem:

Output:

Solution:

Problem:

Output:

Solution:

Problem:

Output:

Solution:

Problem:

Output:

Solution:

Problem:

Solution:

Problem:

Output:

Solution:

Problem:

Output:

Solution:

Problem:

Output:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Follow Me

Subscribe

Upload Material