Discussion on Two Two Challenge

9 years ago+ 3 comments

I concur. I did it in Java, using a trie for the 801 strings. Iterated through the test string, applying the trie at each location.

I did not need to implement the Aho-Corasick failure optimisations to meet the timing constraints.

9 years ago+ 1 comment

My first attempt at brute forcing timed out (shocker!), but a simple trie worked like a charm. Thanks for the tip ;)

5 years ago+ 0 comments

How did you solve timeout problem they should have pass test then should about required time limit

import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.concurrent.atomic.AtomicInteger; import java.util.function.Consumer; import java.util.function.Function; import java.util.function.Predicate; import java.util.regex.*; import java.util.stream.Collectors;

public class Solutions {

private static final Scanner scanner = new Scanner(System.in);


static Map<BigInteger,Integer> powervalueMap = new HashMap<>();
public static int twoTwo (String input) {

    int result = 0;
    if(input==null|| input=="") {
        return 0;
    }
    int len=input.length();



//List<String> dataSet= breakInSets(input);
 int foundcounter=0;
// int klen=dataSet.size();
 String data="";
 /*
 long t1=System.nanoTime();

for(int k=0;k 0) { //System.out.println("data="+data); BigInteger val=new BigInteger(""+data); if(isPower2(val)) { foundcounter++; } } }; long t2=System.nanoTime(); System.out.println("1. total time"+(t2-t1)); */ // final AtomicInteger resultSai = new AtomicInteger(0); // Parallel stream implementation //long countsai = dataSet.stream().filter(Solutions::isPower22).count();

// Predicate<Integer> lesserthandiv2 = i -> (isDividenby2(i));

//.....Predicate<String> p1 = c -> ( isPower22(c));
//..List<String> dataSet2=  breakInSets(input);
//t1=System.nanoTime();
//long foundcounter1=dataSet2.parallelStream().filter(p1).count();//forEach(){xa->if(isPower22(xa  )) {};};
//.................long foundcounter1=dataSet2.stream().filter(p1).count();
int foundcounter1=breakInSetsCount(input);
 //t2=System.nanoTime();
 //System.out.println("2. total time"+(t2-t1));
        //print(" strem way count sai ji "+countsai1);
//Function<Integer> fun = x->(x*3);

//dataSet2.stream().filter(p1).map( xx-> xx*3 ).count();

if(foundcounter1>0) {
    result=(int)foundcounter1;
}
//System.out.println("foundcounter="+foundcounter);
    return result;
}


public static boolean isPower22(String str  ) {

    //print("isPower22 input... "+str);
    if(str==""||str ==null||str==" "||" ".equals(str)||str.length() ==0) {
        return false;
    }
    BigInteger number = new BigInteger(str);

     boolean  flag =false;

        for( BigInteger x: powervalue) {
            //print(" x="+x+" number"+number);
        if(x.compareTo(number) ==0) {
            //print("mtch found  IF x="+x+" number"+number);
            flag=true;
            break;
        }else if(x.compareTo(number) > 0) {//x>n
            break;
        }else {
            //print("else  x="+x+" number"+number);
        }
    }
        //print(number+" flag "+flag);
    return flag;
}

public static boolean isPower22Map(String str ) {

    //print("isPower22 input... "+str);
    if(str==""||str ==null||str==" "||" ".equals(str)||str.length() ==0) {
        return false;
    }
    BigInteger number = new BigInteger(str);

     boolean  flag =false;
if(powervalueMap.get(number)!=null) {
    return true;
}

    return flag;
}
//
public static boolean isPower2(BigInteger number ) {

     boolean  flag =false;

        for( BigInteger x: powervalue) {
            //print(" x="+x+" number"+number);
        if(x.compareTo(number) ==0) {
            //print("mtch found  IF x="+x+" number"+number);
            flag=true;
            break;
        }else if(x.compareTo(number) > 0) {//x>n
            break;
        }else {
            //print("else  x="+x+" number"+number);
        }
    }
        //print(number+" flag "+flag);
    return flag;
}

public static boolean powersetFLag =false;
public static BigInteger  powervalue[]=new BigInteger[800];

public static int breakInSetsCount(String inpurMsg) {
    inpurMsg=inpurMsg+" ";

    int  result = 0;
    if(inpurMsg!="" ||inpurMsg!=null  ) {
        int len =inpurMsg.length();
        for(int i=0; i < len;i++) {
            //let 1,2,3,4
            String temp=inpurMsg.substring(i);
            int len2 =temp.length();
            if(len2>0 &&!"0".equals(temp.substring(0,1))&& !" ".equals(temp.substring(0,1))) {

            for(int j=0;j < len2;j++) {

                if(isPower22Map(temp.substring(0,j))) {

                    result++;
                }
            }
            }
        }

    }
    //System.out.println(" result >>>>>>>>>>>>>>>>>>>>>"+result);
    return  result;
}

public static List<String> breakInSets(String inpurMsg) {
    inpurMsg=inpurMsg+" ";

    List<String> result = new ArrayList<String>();
    if(inpurMsg!="" ||inpurMsg!=null  ) {
        int len =inpurMsg.length();
        for(int i=0; i < len;i++) {
            //let 1,2,3,4
            String temp=inpurMsg.substring(i);
            int len2 =temp.length();
            if(len2>0 &&!"0".equals(temp.substring(0,1))&& !" ".equals(temp.substring(0,1))) {

            for(int j=0;j < len2;j++) {
                result.add(temp.substring(0,j));
            }
            }
        }

    }

    return  result;
}

public static void setPowers() {

    if(!powersetFLag) {
        powersetFLag=true;
        for( int i =0; i < 800;i++) {
            //powervalue[i]=(BigInteger)Math.pow(2, i+1);

            powervalue[i]= BigDecimal.valueOf(Math.pow(2, i+1)).toBigInteger();
        }
    }
}

public static void setPowersMap() {


        for( int i =0; i < 800;i++) {
            //powervalue[i]=(BigInteger)Math.pow(2, i+1);

            powervalueMap.put( BigDecimal.valueOf(Math.pow(2, i+1)).toBigInteger(),1);
        }

}
static int camelcase(String s) {
    if(s==null||s=="" ||s.length()==0) {
        return 0;
    }

int result =1; char[] arr=s.toCharArray(); char[] al= {'Q','W','E','R','T','Y','U','I','O','P','A','S','D','F','G','H','J','K','L','Z','X','C','V','B','N','M'}; for( int i=0; i < arr.length;i++) { for( int j=0;j< 26;j++) { if(arr[i]==al[j]) { result++; } } } return result; }

public static void main(String[] args) throws IOException {
    setPowers();
    setPowersMap();;
    System.out.println(powervalueMap);
    /*
     2222222

24256 65536 023223 33579 */ print("**************************2222222 result ..."+twoTwo("2222222")); print("****************************24256 result "+twoTwo("24256")); print("****************************5665536 result "+twoTwo("5665536")); print("********************023223 result "+twoTwo("023223")); print("******************33579 result "+twoTwo("33579")); String sai=""; ; ; //BigInteger k = BigDecimal.valueOf(doublevalue).toBigInteger(); sai="9223372036854775807"; print("****************"+sai); print(".............."+twoTwo(sai)); //print("max value "+Math.pow(2,Integer.MAX_VALUE)); //print(".............."+twoTwo(""+Math.pow(2,Integer.MAX_VALUE))); /* print("24256");BigInteger print(breakInSets("24256")); print("1"); print(breakInSets("1")); print("12"); print(breakInSets("12")); print("123"); print(breakInSets("123")); print("1234"); print(breakInSets("1234")); print("12345"); print(breakInSets("12345"));

print("123456");
print(breakInSets("123456"));



*/

print("023223");
print(breakInSets("023223"));
}




static void print(Object[] a) {
    System.out.print("  \n");
    for (int i = 0; i < a.length; i++) {
        System.out.print("  " + a[i]);
    }
}
static void print(List a) {
    System.out.print("  \n");
    for (int i = 0; i < a.size(); i++) {
        System.out.print("  " + a.get(i));
    }
}
static void print(int[] a) {
    System.out.print("  \n");
    for (int i = 0; i < a.length; i++) {
        System.out.print("  " + a[i]);
    }
}
static void print(BigInteger[] a) {
    System.out.print("  \n");
    for (int i = 0; i < a.length; i++) {
        System.out.print("  " + a[i]);
    }
}
static void print(int a) {

    System.out.print(" \n " + a);

}

static void print(String a) {

    System.out.println("\n"+ a);

}

}

7 years ago+ 1 comment

I tried trie method but some cases are still giving 'timeout' output and no. of cases that show 'timeout' error differ each time I hit 'Submit Code' button.

7 years ago+ 1 comment

HINT: Don't search the trie with each sub-string. Don't implement a separate search function at all.

6 years ago+ 0 comments

Thanks. With a standard Trie, I passed 8 tests (0-7) and timed out on the rest. When I modified the code to manually walk the Trie as I progressed through the substrings for a given i strarting position, including some conditional checking to break the j loop early as appropriate, I passed all but 2 tests on the next submission, then resubmitted without changes and passed all tests (so 2 of mine must be right on the edge of the acceptable time boundary).

Sidenote: I used the java.math.BigInteger class and its multiply method in a loop to find the 801 powers of 2, and in each iteration used its toString method to get the String to use for inserting into the Trie. Perhaps using Strings alone and a custom method to compute the powers of 2 might have been faster.

6 years ago+ 0 comments

why don't you use big-integer class in java

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge