Geek Answers Handbook

Find all integers in a string of numbers that match the criteria

I'm trying to come up with an algorithm in Java that, when given a string of numbers, can identify a combination of integers that matches the following criteria

  • N = N1 + N2
  • N> = N1> = N2
where:
   N is the Nth element in the string or element at Nth position;
   N1 is the (N-1) element in the string & N2 is the (N-2) element in the string.

Example 1: 224610
Elements in this string are 2, 2, 4, 6, 10.
First Set:     2+2=4 (N2=2; N1=2 & N= 4);
Second Set: 2+4=6 (N2=2; N1=4 & N=6);
Third Set:    4+6=10 (N2=4; N1=6 & N= 10)

Example 2: 11112233558
Elements in this string are 1, 11, 12, 23, 35, 58

Example 3: 1101102203
Elements in this string are 1, 101, 102, 203.

I already wrote a function that can take an ArrayList of integers and tell you if the array meets the requirements.

public static boolean complies(ArrayList<Integer> al)
{
     boolean result = true;
     int alsize = al.size();

     for (int n = alsize-1; n > 1; n--)
     {
         int N1 = al.get(n-1);
         int N2 = al.get(n-2);
         int N = al.get(n);
         if (N != ( N1 + N2))
            result  = false;
         if ((N < N1) || (N1 <  N2))
            result  = false;
     }
     return(result);
}

The part with which I struggle to find an elegant way to identify all possible integer combinations that I can perform using the above function.

+4
source share
3 answers

, , , , , . , , , , . , , , , , .

. 123 23, 23 , 3, 3. 2 , 2, 3 2 , 23. 1 , 1, 2, 3 1, 23, 1 , 12, 3 123.

, , . List arrayList, . , . , -. , List , List . .

public ArrayList<ArrayList<Integer>> findCombos(String input) 
{
    ArrayList<ArrayList<Integer>> answer = new ArrayList<ArrayList<Integer>>();
    if(input.length()==1)
    {
        ArrayList<Integer> combo = new ArrayList<Integer>();
        answer.add(combo);
        combo.add(Integer.parseInt(input));  //this method converts from a string to an int
        return answer;
    }
    else
    {
        answer = findCombos(input.substring(1));
        int size = answer.size();  //you need to save this because when you add things to an arrayList the size changes
        for(int i=0;i<size;i++) //this copies the arrayList back to itself
        {
            ArrayList<Integer> copy = new ArrayList<Integer>(answer.get(i));
            answer.add(copy);
        }
        int digit = (char)(input.charAt(0)-'0');//this saves the current digit
        for(int i=0;i<size;i++)//this adds the digit in front of all the previous combos
            answer.get(i).add(0, digit);
        for(int i=size;i<answer.size();i++)//this puts the digit in front of the first term of the previous combos
        {
            String copy = "" + answer.get(i).get(0);//I just did this to find the length of the first term easily
            int append = (int)(digit*Math.pow(10, copy.length()));
            answer.get(i).set(0, append+answer.get(i).get(0));
        }
        return answer;
    }
}
0

.

    public class IntFinder
    {

        /**
         * @param args the command line arguments
         */
        private static String given = "444444889321420";
        static N1N2 temp = new N1N2(given);

        public static void main(String[] args) {
            // TODO code application logic here
            N1N2 n1 = new N1N2(given);
            N1N2 n2 = new N1N2(given);

            /*IntFinder.setGiven("224610");
            n1 = new N(IntFinder.getGiven());
            n2 = new N(IntFinder.getGiven());
            n1.setValue(0, 0); // 2
            n2.setValue(1, 1); // 2*/

            /*IntFinder.setGiven("11112233558");
            n1 = new N(IntFinder.getGiven());
            n2 = new N(IntFinder.getGiven());
            n1.setValue(0, 0); // 1
            n2.setValue(1, 2); // 11*/

            IntFinder.setGiven("1101102203");
            n1 = new N1N2(IntFinder.getGiven());
            n2 = new N1N2(IntFinder.getGiven());
            n1.setValue(0, 0); // 1
            n2.setValue(1, 3); // 101

            System.out.println("string: " + n1.getValue());
            System.out.println("string: " + n2.getValue());
            System.out.println("result: " + ((IntFinder.findTillEndByN1N2(n1, n2) > -1) ? "found" : "NOT found"));
        }

        public static String setGiven(String givenString)
        {
            return IntFinder.given = givenString;
        }

        public static String getGiven()
        {
            return IntFinder.given;
        }

        public static int findTillEndByN1N2(N1N2 n1, N1N2 n2)
        {
            int retVal = -1, lenChange = n1.getLength() + n2.getLength() + n1.getStartIndex();

            retVal = findNagainstN1N2(n1, n2, lenChange);

            if (IntFinder.getGiven().length() == (n2.getEndIndex() + 1)) // base case 1 (last digit reached)
            {
                return 1;
            }
            else if (IntFinder.getGiven().length() < (n2.getEndIndex() + 1))
            {
                System.out.println("fatal err:");
                System.exit(0);
            }

            if (retVal > -1) // recurse till end
            {
                if (!temp.getUsed())
                {
                    temp = IntFinder.shallowCopy(n1);
                    temp.setUsed(true);
                }
                n1 = IntFinder.shallowCopy(n2);
                n2.setValue(n2.getEndIndex() + 1 , retVal);
                System.out.println("string: "+n2.getValue());
                retVal = findTillEndByN1N2(n1, n2);
            }
            else
                return retVal;
            return retVal;
        }

        public static Integer findNagainstN1N2(N1N2 n1, N1N2 n2, Integer startIndex)
        {
            String remainingGiven = IntFinder.getGiven().substring(startIndex);
            Integer i, n1n2Total = 0, retVal = -1;
            n1n2Total = n1.getValue() + n2.getValue();
            for (i = 0; i < remainingGiven.length(); i++)
            {
                try
                {
                    int found = Integer.parseInt(remainingGiven.substring(0, (i+1)));


                    if (found == n1n2Total)
                    {
                        retVal = startIndex + i;
                        break;
                    }
                    else if (found > n1n2Total)
                    {
                        retVal = -1;
                        break;
                    }
                }
                catch (NumberFormatException e)
                {
                    ;
                } 
            }
            return retVal;
        }

        public static N1N2 shallowCopy(N1N2 from) {
            N1N2 newN = new N1N2(IntFinder.getGiven());
            newN.setValue(from.getStartIndex(), from.getEndIndex());
            return newN;
        }
    }


>>N1N2.class

    public class N1N2 {
        private String givenString;
        private int startIndex = 0;
        private int endIndex = -1;
        private int value = 0;
        private int length = endIndex + 1;
        private Boolean used = false;

        public N1N2(String given) {
            startIndex = 0;
            endIndex = given.length() - 1;
            givenString = given;
        }

        public int getValue() {
            return value;
        }

        public int getLength() {
            return length;
        }

        public Boolean getUsed()
        {
            return used;
        }

        public void setUsed(Boolean used)
        {
            this.used = used;
        }

    //    public void outValues()
    //    {
    //        System.out.println("given:" + givenString + ", startIndex:"+ startIndex + ", endIndex: " + endIndex + ", length:" + length + ", value:" + value + "\n");
    //    }

        public void setValue(int startIndex, int endIndex) {
            this.value = Integer.parseInt(givenString.substring(startIndex, endIndex + 1));
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            this.length = (this.value + "").length();
    //        this.outValues();
        } 

        public int getEndIndex() {
            return this.endIndex;
        }

        public int getStartIndex() {
            return this.startIndex;
        }
    }

n1 n2 , IntFinder.findTillEndByN1N2 (n1, n2).

, .

, , , ,

n1.setValues ​​ n2.setValues ​​

Ex.

given = 1232447
//first loop
n1.setValues(0,0) // value = 1
n2.setValues(1,1) // value = 2
IntFinder.findTillEndByN1N2(n1, n2) // returns -1 // not found...

//next loop - increment n2 length
n1.setValues(0,0) // value = 1
n2.setValues(1,2) // value = 23
IntFinder.findTillEndByN1N2(n1, n2) // returns 1 // now found till end.


//ofcourse when n2 reached the last digit, increment n1 length by 1 and set n2 length back to 1.

//for given=444444889321420 // 44 444 488 932 1420
//all findTillEnd with n1 length 1 should fail so inc n1 length on outer loop
//n1.setValue(0, 1) // 2 digit number ( 44)
//n2.setValue(0, 0) // 4

//upon continuing loop, the desired result will be met.
0

In accordance with the above solution from Pham, I can change the code to exclude cases of edges and create a solution for the above question. This method will always return true if it matches the else false pattern and yes, we must find the first two elements to make it work. Checked for all test cases:

public static boolean complies(String input){
    // List<Long> firstTwo = new ArrayList<Long>();
    for(int i = 1; i < input.length(); i++){
        for(int j = 0; j < i; j++){
            long first = Long.parseLong(input.substring(0, j + 1));//substring form 0 to j
            long second = Long.parseLong(input.substring(j + 1, i + 1));//substring from j + 1 to i
            if(second < first)
                  continue;

            String last = "" + first + second;
            System.out.println("first :"+first+" second :"+second);
            if(last.length() == input.length()){
                return false;
            }
           // firstTwo.add(first);
           // firstTwo.add(second);
            while(last.length() < input.length()){
                  long nxt = first + second;
                  last += nxt;
                  first = second;
                  second = nxt;
            } 
            if(last.equals(input)){//Matched!
                System.out.println("matched");
                // dont go further return true
                return true;
            }
           // firstTwo.clear();
        }
    } 
    return false;
}
0
source

More articles:


All Articles