CODEWITHSUNDEEP
javaalgorithm
pshemek
pshemek

Reputation: 1419

java codility Frog-River-One

I have been trying to solve a Java exercise on a Codility web page.

Below is the link to the mentioned exercise and my solution.

https://codility.com/demo/results/demoH5GMV3-PV8

Can anyone tell what can I correct in my code in order to improve the score?

Just in case here is the task description:

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.

You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

For example, you are given integer X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

In minute 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

class Solution { public int solution(int X, int[] A); }

that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

the function should return 6, as explained above. Assume that:

N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

And here is my solution:

import java.util.ArrayList;
import java.util.List;

class Solution {

    public int solution(int X, int[] A) {
        int list[] = A;
        int sum = 0;
        int searchedValue = X;

        List<Integer> arrayList = new ArrayList<Integer>();

        for (int iii = 0; iii < list.length; iii++) {

            if (list[iii] <= searchedValue && !arrayList.contains(list[iii])) {
                sum += list[iii];
                arrayList.add(list[iii]);
            }
            if (list[iii] == searchedValue) {
                if (sum == searchedValue * (searchedValue + 1) / 2) {
                    return iii;
                }
            }
        }
        return -1;
    }
}

Upvotes: 16

Views: 55387

Answers (30)

Nazariy Vlizlo
Nazariy Vlizlo

Reputation: 977

Swift 100% solution:

public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int {
    Int(ceil(Double(Y - X) / Double(D)))
}

Upvotes: 0

Mike
Mike

Reputation: 41

My solution (score = 100)

import java.util.*;

public int solution(int X, int[] A) {
    Set<Integer> pos = new HashSet<>();
    int highestTime = 0;
    // Adding to the Set only positions with minimal times
    for(int i = 0; i < A.length; i++){
        if(!pos.contains(A[i])){
            if(A[i] > X) {
                continue;
            }
            pos.add(A[i]);
            if(i > highestTime) {
                highestTime = i;
            }
        }
    }
    if(!pos.contains(X)) {
        return -1;
    }

    // if positions are not consecutive, the frog cannot cross the river
    for(int p = 1; p <= X; p++){
        if(!pos.contains(p)){
            return -1;
        }
    }
    return highestTime;
}

Upvotes: 0

Joe Alex Kimani
Joe Alex Kimani

Reputation: 1

This solution utilizes 2 Sets to compute the solution. Time complexity O(N)

public int solution(int[] A, int X) {
    Set<Integer> requiredLeavesSet = new HashSet<>();
    for (int i = 1; i <= X; i++) {
        requiredLeavesSet.add(i);
    }
    Set<Integer> currentLeavesSet = new HashSet<>();
    for (int i = 0; i < A.length; i++) {
        currentLeavesSet.add(A[i]);
        if (currentLeavesSet.size() < requiredLeavesSet.size()) continue;

        if (currentLeavesSet.containsAll(requiredLeavesSet)) return i;
    }
    return -1;
}

JUnit5 Test Case:

@ParameterizedTest
@MethodSource("createData")
void solutionTest(int numberOfSteps, int[] testInputArray, int expectedValue) {
    assertEquals(expectedValue, frogRiverOne.solution(testInputArray, numberOfSteps));
}

public static Object [][] createData() {
    return new Object [][] {
            new Object [] { 5, new int [] {             1, 3, 1, 4, 2, 3, 5, 4 },  6 },
            new Object [] { 3, new int [] {                               1, 3 }, -1 }, //never gets across
            new Object [] { 2, new int [] {                         1, 1, 1, 1 }, -1 }, //never gets across
            new Object [] { 3, new int [] {                         1, 4, 2, 3 },  3 },
            new Object [] { 2, new int [] {                         1, 4, 2, 3 },  2 },
            new Object [] { 4, new int [] { 1, 2, 3, 2, 3, 3, 1, 2, 2, 4, 2, 1 },  9 },
            new Object [] { 4, new int [] { 1, 2, 3, 2, 3, 3, 1, 2, 4, 4, 2, 1 },  8 },
            new Object [] { 4, new int [] { 1, 2, 3, 4, 3, 3, 1, 2, 4, 4, 2, 1 },  3 },
    };
}

Analysis: Codility Analysis Report

Upvotes: 0

Vladimir D&#237;az
Vladimir D&#237;az

Reputation: 1

Here the solution with C++:

#include <algorithm>
int solution(int X, vector<int> &A) 
{
    vector<bool> boolVec (X,false);
    if(A.size()>0)
    {
       for(unsigned int i=0; i<=A.size()-1; i++)
       {
          // Find in boolean vector
          if (boolVec[A[i]-1] != true)
          {
             boolVec[A[i]-1] = true;
          }
          // All steps done?
          if (all_of(boolVec.begin(), boolVec.end(), [](bool i){return i; }))
          {
             return i;
          }
       }
    }
    return -1;
}

Upvotes: 0

Amit Dhawan
Amit Dhawan

Reputation: 1

Java solution. 100% success on codility

 public int solution(int X, int[] A) {

        boolean[] counter = new boolean[X + 1];
        int count = 0;
        for (int i = 0; i < A.length; i++) {

            if (counter[A[i]] == false) {
                counter[A[i]] = true;
                count++;
                if (count == X) {
                    return i;
                }
            }


        }
        
        return -1;


    }

Upvotes: 0

iosMentalist
iosMentalist

Reputation: 3084

for swift 100%

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
        var main = Set(1...X)
        for (index,item) in A.enumerated(){
            if let _ = main.remove(item){
                if main.count == 0{
                    return index
                }
            }
        }
        return -1
    }

Upvotes: 0

ayu.sheee
ayu.sheee

Reputation: 91

For Javascript to gain 100% score follow this solution!! I have used Set()

    function solution(X, A) {
    
        let Position = new Set();
        let n = A.length;
        for(let i=0;i<n;i++){
             Position.add(A[i]);
             if(Position.size==X)
               return i;
        }
       if(Position.size!=X){
         return -1;  
       }
    }

Upvotes: 0

Sumith Ekanayake
Sumith Ekanayake

Reputation: 2265

in C#

public static int solution(int X, int[] A)
{
    HashSet<int> hash = new HashSet<int>();

    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] <= X)
        {
            hash.Add(A[i]);

            if (hash.Count == X)
                return i;
        }
    }
    return -1;
}

Upvotes: 0

Talha Tayyab
Talha Tayyab

Reputation: 27455

Python #

I am using OrderedDict from collections and sum of first n numbers to check whether the frog will be able to cross or not.

def solution(X, A):
    from collections import OrderedDict as od
    if sum(set(A))!=(X*(X+1))//2:
        return -1
    k=list(od.fromkeys(A).keys())[-1]
    for x,y in enumerate(A):
        if y==k:
            return x

Upvotes: 0

shaikh
shaikh

Reputation: 592

Just another answer using hashsets in Java with 100/100 score.

    public int solution(int X, int[] A) {            
        Set<Integer> positions = new HashSet<>();
        for(int i = 0; i < A.length; i++){
            if(A[i] <= X)
                positions.add(A[i]);
            if(positions.size() == X)
                return i;
        }
        return -1;
    }

Upvotes: 0

Jeff W
Jeff W

Reputation: 59

Another C# approach (similar to that used by Kamlesh Shewani):

using System;
using System.Collections.Generic;

class Solution {
        public int solution(int X, int[] A)
        {
            var set = new HashSet<int>(A);
            return set.Count != X ? -1 : Array.IndexOf<int>(A, new List<int>(set)[new List<int>(set).Count-1]);
        }
}

Upvotes: 0

Kunal
Kunal

Reputation: 51

 public static int solutions(int X, int[] A) {
        Set<Integer> values = new HashSet<Integer>();

        for (int i = 0; i < A.length; i++) {
            if (values.add(A[i])) {
                X--; 
            }
            if (X == 0) {
                return i;
            }
        }
        return -1;
    }

Upvotes: 1

Marcin Kowalczyk
Marcin Kowalczyk

Reputation: 11

https://app.codility.com/demo/results/trainingXE7QFJ-TZ7/

I have a very simple solution (100% / 100%) using HashSet. Lots of people check unnecessarily whether the Value is less than or equal to X. This task cannot be otherwise.

public static int solution(int X, int[] A) {
    Set<Integer> availableFields = new HashSet<>();

    for (int i = 0; i < A.length; i++) {
        availableFields.add(A[i]);
        if (availableFields.size() == X){
            return i;
        }
    }

    return -1;
}

Upvotes: 1

Ayesha
Ayesha

Reputation: 7

HashSet<Integer> _hashset = new HashSet<Integer>();
        int occupiedPositions = 0;

        for (int i = 0; i < A.length; i++)
        {
            if(A[i] <= X && _hashset.add(A[i]))
            {
                occupiedPositions++;
            }

            if (occupiedPositions == X)
                return i;
        }

        return -1;

}

Upvotes: 0

amirul
amirul

Reputation: 430

I think this solution would be easy to understand. If you need to know elaborate . Please let me know which part do you want to know.

    static int solution(int x, int[]a){

    int currentPosition = 0;//The frog is initially located on one bank of the river (position 0) 
    int[] opositPostion = new int[x+1];//wants to get to the opposite bank (position X+1). 

    for(int i = 0; i < a.length; i++){

        if (opositPostion[a[i]]== 0){
            opositPostion[i] = a[i];
            currentPosition += 1;
        }
        if (currentPosition == x){//The goal is to find the earliest time when the frog can jump to the other side of the river.
            return i;
        }
    }

    return -1;

}

Upvotes: 0

Anand Kulkarni
Anand Kulkarni

Reputation: 435

Here is a unique solution [ already not listed in above using multi map in C++]. This scores 100% on codility and detected big(O) complexity is O(N). Esentially build a multi map of position and list of times [ i.e seconds ] at which leaves fall at that position.

int solution(int targetPos, vector<int>& A)
{
  if(!A.size())
    return(-1);

  multimap<int, int> positionMap;
  bool insertStatus=false;
  for(size_t i=0;i<A.size();++i)
  {
    positionMap.insert(pair<int, int>(A[i], i));
    if(targetPos==A[i])
      insertStatus=true;
  }

  if(!insertStatus)
    return(-1);

  int currMax=-1;
  for(int i=1; i<=targetPos;++i)
  {
    auto iter=positionMap.equal_range(i);
    if(!distance(iter.first, iter.second))
      return(-1);

    int currMin=INT_MAX;
    for(auto it=iter.first; it!=iter.second; ++it)
    {
      if(it->second<currMin)
        currMin=it->second;
    }
    if(currMin>currMax)
      currMax=currMin;
  }

  return(currMax);
}

Upvotes: 0

Wisdom Adzorgenu
Wisdom Adzorgenu

Reputation: 11

Javascript solution

function solution(X, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let minTime = -1;
    
    //initial positions with leafs
    let posFilled = Array(X+1).fill(false);
    let totalFilled = 0;

    for(let i=0; i<A.length; i++){
        let step = A[i];
        
        //if already filled, don't add to total filled
        if(step <= X && !posFilled[step]) {
            posFilled[step] = true;
            
            //increment total filled
            totalFilled += 1;
        }

        //if all have been filled, set min time and break        
        if(totalFilled === X){
            minTime = i;
            
            break;
        }
    }
    
    return minTime;
}

Upvotes: -1

yi.han
yi.han

Reputation: 379

C# Solution with 100% score:

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int X, int[] A) {
        // go through the array
        // fill a hashset, until the size of hashset is X
        var set = new HashSet<int>();
        int i = 0;
        foreach (var a in A)
        {
            if (a <= X)
            {
                set.Add(a);
            }
            if (set.Count == X)
            {
                return i;
            }
            i++;
        }
        return -1;
    }
}

Upvotes: 2

Ravi Ranjan Kumar Jha
Ravi Ranjan Kumar Jha

Reputation: 21

Here is my answer in Python:

def solution(X, A):
    # write your code in Python 3.6
    values = set()
    for i in range (len(A)):
        if A[i]<=X :
            values.add(A[i])
        if len(values)==X:
            return i
    return -1

Upvotes: 2

remacr
remacr

Reputation: 708

100% Solution using Javascript.

enter image description here

function solution(X, A) {
    if (A.length === 0) return -1
    if (A.length < X) return -1


    let steps = X
    const leaves = {}
    for (let i = 0; i < A.length; i++) {
        if (!leaves[A[i]]) {
            leaves[A[i]] = true
            steps--
        }

        if (steps === 0) {
            return i
        }
    }

    return -1
}

Upvotes: 1

rafalio
rafalio

Reputation: 3946

You are using arrayList.contains inside a loop, which will traverse the whole list unnecessarily.

Here is my solution (I wrote it some time ago, but I believe it scores 100/100):

    public int frog(int X, int[] A) {
        int steps = X;
        boolean[] bitmap = new boolean[steps+1];
        for(int i = 0; i < A.length; i++){
            if(!bitmap[A[i]]){
                bitmap[A[i]] = true;
                steps--;
                if(steps == 0) return i;
            }

        }
        return -1;
    }

Upvotes: 51

AbdurrahmanY
AbdurrahmanY

Reputation: 883

With JavaScript following solution got 100/100.

Detected time complexity: O(N)

function solution(X, A) {
    let leaves = new Set();

    for (let i = 0; i < A.length; i++) {
        if (A[i] <= X) {
            leaves.add(A[i])
            if (leaves.size == X) {
                return i;
            }
        }
    }
    return -1;    
}

Upvotes: 1

saygin
saygin

Reputation: 11

%100 with js

function solution(X, A) {

  let leafSet = new Set();

  for (let i = 0; i < A.length; i += 1) {

    if(A[i] <= 0) 
        continue;

    if (A[i] <= X )
        leafSet.add(A[i]); 


    if (leafSet.size == X)
      return i;

  }

  return -1;
}

Upvotes: 1

Dinakar Prasad Maurya
Dinakar Prasad Maurya

Reputation: 371

Frogt Reiver One Codility 10%

With little explanation in python codility 100 %

def solution(X, A):
"""
https://app.codility.com/demo/results/trainingQ28RU6-FFE/
100%
idea is use array item as K_index in covered time array
covered time array set the value to be covered as soon as it finds some value
if position is already covered it checks for all items in array until any of the item in array can be covered
:param X:
:param A:
:return:
"""
# assume all position is covered
covered_time = [-1] * X
for K_index in range(0, len(A)):
    print("Covered position count " + str(X))
    print(X)
    print(covered_time)
    if covered_time[A[K_index] - 1] != -1:
        # A[K] represents the position where one leaf falls at time K
        # position is already covered
        # time is being spent
        continue
    else:
        # This position is to be covered
        # cover this position ie. make array element with marker(array value)
        covered_time[A[K_index] - 1] = K_index
        # reduce position to be cover
        X -= 1
        # as soon as positions are covered return
        if X == 0:
            # now all positions are covered
            return K_index
# if we are here it means time spent but we can not cover all positions
return -1


result = solution(5, [1, 3, 1, 4, 2, 3, 5, 4])
print("Sol " + str(result))

Upvotes: 0

Flavio
Flavio

Reputation: 1705

Yet another 100% Score whith Java:

class Solution {
    public int solution(int X, int[] A) {
        int leafs[] = new int[X];
        int count = X;
        for (int i = 0; i < A.length; i++)
        {   
            if (leafs[A[i]-1] != 1)
            {
                leafs[A[i]-1] = 1;
                count--;
            }
            if (count == 0)
                return i;
        }
        return -1;
    }
}

Upvotes: 0

Luke Samad
Luke Samad

Reputation: 11

This one works good on codality 100% out of 100%. It's very similar to the marker array above but uses a map:


  public int solution(int X, int[] A) {
    int index = -1;

    Map<Integer, Integer> map = new HashMap();
    for (int i = 0; i < A.length; i++) {
      if (!map.containsKey(A[i])) {
        map.put(A[i], A[i]);
        X--;
        if (X == 0) {index = i;break;}
      }
    }

    return index;
  }

Upvotes: 1

Yolisa Ennocent
Yolisa Ennocent

Reputation: 11

This loops array A and inserts data to array B (1) to every position that the content in A points to..

If A[0] = 4, then at B[4-1] = 1, do this until var = X. 

public static int bestSolution(int X, int[] A) {
        int[] B = new int[X];
        int var = 0;
        for (int i = 0; i < A.length; i++) {
            int content = A[i];
            if (B[content - 1] == 0) {
                B[content - 1] = 1;
                var++;
            }
            if(var == X){
                return i;
            }
        }
        return -1;
    }

Upvotes: 0

Nick
Nick

Reputation: 447

My JavaScript solution that got 100 across the board. Since the numbers are assumed to be in the range of the river width, simply storing booleans in a temporary array that can be checked against duplicates will do. Then, once you have amassed as many numbers as the quantity X, you know you have all the leaves necessary to cross.

function solution(X, A) {
    covered = 0;
    tempArray = [];
    for (let i = 0; i < A.length; i++) {
        if (!tempArray[A[i]]) {
            tempArray[A[i]] = true;
            covered++
            if(covered === X) return i;
        }
    }
    return -1;
}

Upvotes: 2

faizal khan
faizal khan

Reputation: 105

import java.util.Set;
import java.util.HashSet;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int X, int[] A) {
     Set<Integer> positionsCovered = new HashSet<Integer>(); 
//Set covering the leaves fallen to keep track of the distance to destination   

        if(X == 1)
             return 0 ;
       int position = 0;     
       for(int i = 0; i < A.length -1 ;i++ ) {       
           if(A[i] <= X && A[i] > 1 && positionsCovered.size() < (X-1)) { 
      //X-1 as we start from 1
               positionsCovered.add(A[i]);
           }
           if(positionsCovered.size()== (X-1)) {
               position = i ;
            break;
           }
       }         
        return position != 0 ? position : -1;
    }
}

Upvotes: 0

Mohamed.Emad
Mohamed.Emad

Reputation: 1

 private static int FrogRiverOne(int X, int[] A)
        {
            HashSet<int> occ = new HashSet<int>();
            for (int i = 0; i < A.Length; i++)
            {
                if (A[i] <= X)
                {
                    occ.Add(A[i]);
                }
                if (occ.Count == X)
                    return i;
            }
            return -1;}

Upvotes: -1

Related Questions