Codility FibFrogg

Idea: This is a search graph task. A used this explanation of the algorithm LINK.

In first step you check all possible single jumps from start point. This creates a new "row" of starting positions.
In next step you check all possible single jumps from every start position in the "row".
Sum of found new positions create another row.
You skip if you find a possible jump to the position which was "visited" previously, because there is a shorter or equal path to that position.
You stop when any jump will reach "end position" or you cant find a position to jump anymore. Code:

Codility-CommonPrimeDivisors version by PrimeFactorization

It's much slower solution than by using Greatest Common Divisor, but it's different and still gets 100% on Codility platform

Codility-CommonPrimeDivisors version by GCD

It's tricky task. I used some help via internet.
Idea:  Greatest common divisor of A and B consists of EVERY prime divisor of A & B. Consists or contains. There is no such a number E that would be prime, and divisor of A and B that GCD(A,B) * E = A && GCD(A,B) * E =B

Once you have GCD, you divide a number by it. That number can be considered as a "row" of prime factors and their exponents. So dividing number by GCD will remove some factors or their exponents.

Then you create a new GCD value form divided number and old GCD value. And repeat dividing. Eventually GCD will become = 1. Then there are two possibilities:
(last) divided number = 1 number consisted only with prime divisors contained in original GCD
(last) divided number != 1 number consists of some more prime divisors than original GCD

Codility ChocolatesByNumbers

Codility CountSemiprimes solution 2

Codility CountSemiprimes solution 1

Codility - CountNonDivisible

Idea:
Take an element.
Count amount divisors it has.
Non-divisors = N - amount_of_divisors

import static java.lang.Integer.max;
import java.util.Arrays;
class Solution {
  public int[] solution(int[] A) {
    final int N = A.length;
    final int MAX_VALUE_TBL = 2*50000;
    int[] r = new int[N];                     // result table
    int[] AS_AV = new int[MAX_VALUE_TBL + 1]; // number of cell with values

    int[] AS_AR = new int[MAX_VALUE_TBL + 1]; // results yet counted for values
    boolean[] b = new boolean[MAX_VALUE_TBL + 1]; // if value has been counted

    if (N == 1) return r;

    for (int i = 0; i < N; i++) {
      int v = A[i];
      AS_AV[v]++;
    }

    for (int i = 0; i < N; i++) {
      int cu_val = A[i];
      if (!b[cu_val]) {
        int am_div = getAmDivisors(cu_val, AS_AV);
        int am_all = N;
        r[i] = am_all - am_div;
        b[cu_val] = true;
        AS_AR[cu_val] = r[i];
      } else {
        r[i] = AS_AR[cu_val];
      }
    }
    return r;
  }

  private int getAmDivisors(int cu_val, int[] AS_AV) {
    int r = 0;
    int sqr = (int) Math.sqrt(cu_val);

    for (int divisor = sqr; divisor > 0; divisor--) {
      if (cu_val % divisor == 0) {
        r += AS_AV[divisor];
        if (divisor * divisor != cu_val) {
          r += AS_AV[cu_val / divisor];
        }
      }
    }
    return r;
  }
}

Codility - Flags

This is a solution for Codility Flags task:

Idea.

• Register all peaks.
• Maximum flag number is Math.sqrt(idxOfLastPeak - idxOfFirstPeak)+1
• Go through possible flag numbers, starting from maximum downwards. Check every time number of possible flags. 
• If number of possible flags >= number tested (taken) than return number.

 

import static java.lang.Integer.min;

class Solution {
  public int solution(int[] A) {
    int r = 0;
    final int N = A.length;
    int[] P = new int[N / 2];
    int iP = -1;
    int max_flag_number;

    for (int i = 1; i < N - 1; i++) {
      if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
        P[++iP] = i;
      } 
    }

    if (iP == -1)
      return 0;
    if (iP == 0) 
      return 1;

    max_flag_number = (int) (Math.sqrt(P[iP] - P[0])+1);
    for (int flag_taken = max_flag_number; flag_taken > 0; flag_taken--) {
      int possible_nb_flag = countFlag(P, flag_taken, iP);
      if (possible_nb_flag >= flag_taken) {
        r = min(possible_nb_flag, flag_taken);
        break;
      }
    }

    return r;
  }
  
  private int countFlag(int[] P, int space, int iP) {
    int r = 1;
    int start_flag;

    start_flag = P[0];
    for (int i = 1; i <= iP; i++) {
      if (P[i] - start_flag >= space) {
        r++;
        start_flag = P[i];
      }
    }
    return r;
  }
}

Codility Peaks v2

This is the second solution for Codility task, named Peaks.

The idea is simple:
I collect all the "peaks", and meanwhile I notice prefix sum of peak encounters.
I go through possible sizes of division as long, as I find that one, that has at least one peak in every "block" aka division.
============================================

public int solution(int[] A) {
      int r = 0;              // result
      final int N = A.length; // size of input table
      int[] P = new int[N/2]; // peaks
      int pInd = -1;          // last index of peaks table
      int[] S = new int[N];   // sumprefix of peak count
     
      for(int i = 1; i < N-1; i++){
        if(A[i] > A[i-1] && A[i] > A[i+1]){
          P[++pInd] = i;      // remember peak index
          S[i] = S[i-1]+1;    // remember amount of peaks till this idx
        } else {
          S[i] = S[i-1];
        }
      }
      if(pInd == -1) return 0;   // no peaks
      if(pInd ==  0) return 1;   // one peak means one block
     
      S[N-1] = S[N-2];        // filling the last value of S
     
      int minSize = max(N - P[pInd], P[0]+1); // first and last block has to have a peak
      for(int size = minSize; size <=N; size++){
        boolean noPeak = false;
        if(N % size == 0){
          int blocksAmount = N/size;
          for(int blockNb = 1; blockNb < blocksAmount; blockNb++){
            if( !(S[(blockNb+1)*size -1] > S[blockNb*size -1]) ){
              noPeak = true;
              break;
            }
          } // end of loop for blocks
          if (!noPeak) {
            r = N / size;
            break;
          }
        }
      } // end of loop for sizes
     
      return r;
    }

Codility - Peaks

This is the first solution of the peaks task form Codility platform:

Idea is to determine min and max size of possible block, then go through peaks and increase minimum size of the block if some peak is "out of the division". Additionally there is a list of forbidden value of sizes to avoid situation that increasing minimum size on one peak would negatively interfere with any of previous peaks.

It's very long in implementation, but intuitive, very fast && maybe original. Faster than widely published version with checking all the peaks in a loop of consecutive size of the block, if one don't use prefix sum for counting blocks. Of course 100% in Codility test.

Here is a code:


public int solution(int[] A) {
    int r;
    final int N = A.length;
    int[] B = new int[N]; // space between peaks +1
    int[] P = new int[N]; // peaks idxs
    int iP;               // max index of values in table P
    int max_bl, min_bl;
    List<Integer> list_impossible_min = new ArrayList<>();
    int[] min_max_ip = new int[3]; // temporary storage for variables

    // detemine B, P, iP, max_bl, min_bl
    getMinMaxBl(A, B, P, min_max_ip);
    min_bl = min_max_ip[0];
    max_bl = min_max_ip[1];
    iP     = min_max_ip[2];
   
    if(iP == -1){       // no peaks
      return 0;
    } else if(iP == 0){ // one peak
      return 1;
    }

    // applaying last block size
    int last_bl = N-1 -P[iP] + 1;
   
    if( last_bl > min_bl){
      min_bl = last_bl;}
    if(last_bl > B[P[iP]]){
      B[P[iP]] = last_bl;}

    // applying condition of possible divide
    while ((N % min_bl) != 0) {
      min_bl++;}
    while ((N % max_bl) != 0) {
      max_bl++;}


    for (int i = 1; i <= iP; i++) {
      int idx_peak = P[i];
      if (B[idx_peak] > min_bl) {   
        int pp = P[i-1]; // previous peak
       
        int a = (idx_peak + 1) / min_bl;
        int b = a * min_bl;
        if (b != (idx_peak + 1)) { // border of division is in between peaks
          if (b - pp > min_bl) {   // border of division is too far from pp

            // seraching for first possible new min_bl
            for (int j = min_bl + 1; j <= max_bl; j++) {
              a = (idx_peak + 1) / j;
              b = a * j;

              if (list_impossible_min.isEmpty() || !list_impossible_min.contains(j)) {
                if (N % j == 0 && (b - pp <= j)) {
                  min_bl = j;
                  break;
                }
              }
            }
          }
        }
        for (int j = min_bl + 1; j <= B[idx_peak]; j++) {
          a = (idx_peak + 1) / j;
          b = a * j;

          if (N % j != 0 || ((pp + j < idx_peak) && ( b*a-pp > j))) {
            if (pp + j < idx_peak) {
              if (list_impossible_min.isEmpty() || !list_impossible_min.contains(j)) {
                list_impossible_min.add(j);
              }
            }
          }
        }
      }
    }
    r = N / min_bl;

    return r;
  }

  private void getMinMaxBl(int[] A, int[] B, int[] P, int[] min_max_ip) {
    int N = A.length;
    int f_peak = -1, l_peak = -1;
    int iP = -1, min_bl = 0, max_bl = 0;

    // detemine max_bl, min_bl
    // first min_bl & max_bl
    for (int i = 1; i < N - 1; i++) {
      if (peak(A, i)) {
        max_bl = i+1;
        min_bl = i+1;
        f_peak = i;
        l_peak = i;
        B[i]   = i+1;
        P[++iP] = i;
        break;
      }
    }
    if(f_peak > 0){
      for(int i = f_peak+2; i < N-1; i++){
        int t_max_block;
        int t_min_block;
        if (peak(A, i)) {
          t_max_block = i - l_peak; // covers cells max empty space + 1 for peak
          t_min_block = (t_max_block + 1)/2; // covers two peaks + space between
          if((t_max_block+1)%2 != 0){
            t_min_block++;
          }
          min_bl = max(min_bl, t_min_block);
          max_bl = max(max_bl, t_max_block);
          B[i]   = t_max_block;
          l_peak = i;
          P[++iP] = i;
        }
      }
    }
    min_max_ip[0] = min_bl;
    min_max_ip[1] = max_bl;
    min_max_ip[2] = iP;
  }

  boolean peak(int[] A, int i) {
    return A[i] > A[i - 1] && A[i] > A[i + 1];
  }