Showing posts with label hackerrank. Show all posts
Showing posts with label hackerrank. Show all posts

Saturday, July 09, 2016

Consecutive 1s in Integer

Task
Given a base- integer, , convert it to binary (base-). Then find and print the base- integer denoting the maximum number of consecutive 's in 's binary representation.
Input Format
A single integer, .
Constraints

Output Format
Print a single base- integer denoting the maximum number of consecutive 's in the binary representation of .
Sample Input 1
5
Sample Output 1
1
Sample Input 2
13
Sample Output 2
2
Explanation
Sample Case 1:
The binary representation of is , so the maximum number of consecutive 's is .
Sample Case 2:
The binary representation of is , so the maximum number of consecutive 's is .

Analysis:
use and(&) operation with a mask of 1 to tell if right most bit is 1, if it is 1, then a counter will be increased one. and max will try to track the current max length of 1s. otherwise, reset counter.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int max = 0, cnt=0;
        in.close();
        for(int i=0;i<32;i++){
            if((n&1)==1){
                cnt++;//counter 1s
                max = Math.max(max,cnt);//update max consecutive 1s numbers
            }else
                {
                cnt=0;//reset counter
            }
            n=n>>>1;//unsigned shift, so padding it with 0
        }
        System.out.println(max);
    }
}

Wednesday, July 06, 2016

KnapSack, repeat selection

This is similar to coin change problem when it allows multiple selections on items.

Given a list of  integers, , and another integer,  representing the expected sum. Select zero or more numbers from  such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum ().
Note
  • Each element of  can be selected multiple times.
  • If no element is selected then the sum is 0.
Input Format
The first line contains  the number of test cases.
Each test case comprises of two lines. First line contains two integers,  , representing the length of list  and expected sum, respectively. Second line consists of  space separated integers, , representing the elements of list .
Constraints



Output Format
Output  lines, the maximum sum for each test case which is as near as possible, but not exceeding, to the expected sum (k).
Sample Input
2
3 12
1 6 9
5 9
3 4 4 4 8
Sample Output
12
9
Explanation
In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package dp;

import java.util.Scanner;

public class KanpSack {

 public static void main(String[] args) {
  /*
   * Enter your code here. Read input from STDIN. Print output to STDOUT.
   * Your class should be named Solution.
   */
  Scanner in = new Scanner(System.in);
  int t = in.nextInt();
  in.nextLine();
  for (int i = 0; i < t; i++) {
   int n = in.nextInt();
   int k = in.nextInt();
   in.nextLine();
   int[] arr = new int[n];
   for (int j = 0; j < n; j++) {
    arr[j] = in.nextInt();
   }
   in.nextLine();
   process(arr, k);
  }
  in.close();
 }

 private static void process(int[] arr, int k) {
  int max = maxSum(arr, k);
  System.out.println(max);
 }

 private static int maxSum(int[] arr, int k) {
  if (arr == null || arr.length == 0)
   return 0;
  int[] dpSums = new int[k + 1];
  dpSums[0] = 0;
  // for each sum form small to big
  for (int i = 1; i <= k; i++) {
   // for each possible selections, better from small to large
   for (int j = 0; j < arr.length; j++) {
    if (arr[j] <= i) {// when available selection is less or equal
         // than current sum
     // figure out maximum sum the selections can come up
     // second part is important, it is previous sum with
     // possible selection
     dpSums[i] = Math
       .max(dpSums[i], arr[j] + dpSums[i - arr[j]]);
    }
   }
  }
  return dpSums[k];
 }
}

Saturday, July 02, 2016

The Maximum Subarray

The Maximum Subarray


Given an array  of  elements, find the maximum possible sum of a
  1. Contiguous subarray
  2. Non-contiguous (not necessarily contiguous) subarray.
Empty subarrays/subsequences should not be considered.
Input Format
First line of the input has an integer .  cases follow.
Each test case begins with an integer . In the next line,  integers follow representing the elements of array .
Constraints:
  • 1<=T<=10
  • 1<=N<=100000
  • -10000<=ai<=10000
The subarray and subsequences you consider should have at least one element.
Output Format
Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).
Sample Input
2 
4 
1 2 3 4
6
2 -1 2 3 4 -5
Sample Output
10 10
10 11
Explanation
In the first case:
The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).
In the second case:
[2 -1 2 3 4] --> This forms the contiguous sub-array with the maximum sum.
For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.

This is not at all easy, it needs to calculate maximum values for both consecutive and sparse maximum summaries, and you need to know that famous solution to max subarray. Also finally you need to pay attention to how sparse maximum summaries can be calculated.
package DP;

import java.util.Scanner;

/**
 * Created by AndrewLocal on 7/2/2016.
 */

public class MaxSubarray {
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in  =  new Scanner(System.in);
        int N = in.nextInt();in.nextLine();
        for(int i=0;i<N;i++){
            int n = in.nextInt();in.nextLine();
            int a[] = new int[n];
            for(int j=0;j<n;j++)
                a[j]=in.nextInt();
            if(in.hasNextLine())in.nextLine();
            process(a);
        }
        in.close();
    }
    private static void process(int[] a){
        int cSum = a[0];
        int sSum[] = new int[a.length];//sparse, adding numbers only when it makes total bigger
        int cSumMax = a[0];
        //cSum[0]=a[0];
        sSum[0]=a[0];
        for(int i=1;i<a.length;i++){
//-1 2: -1+2>-1 but I'd rather not add -1 to 2 because 1 is less than 2
            sSum[i]=Math.max(sSum[i-1],Math.max(sSum[i-1]+a[i],a[i]));//sparse sum, increase or keep the same
            cSum=Math.max(cSum+a[i],a[i]);//max sum ending here
            cSumMax = Math.max(cSumMax,cSum);//max so far is cSumMax
        }

        System.out.format("%d %d\n",cSumMax,sSum[a.length-1]);
    }

}