Get Immediate Successor in a Given Number Sequence-CodePudding

In an infinite sequence of numbers [2, 5, 7, 22, 25, 27, 52, 55, 57, 72, 75, 77, 222, ...]. Given any number in this sequence get the immediate successor number.

Example:
Input   Output
22      25
77      222
5       7

I have written the below logic to find the next number in a sequence.

public static int getNextNumInSequence(Integer sequenceCurrentNum) {
    List<Integer> sequence = new ArrayList<>();
    sequence.add(2);
    sequence.add(5);
    sequence.add(7);
    
    if(sequence.get(0).equals(sequenceCurrentNum))
        return sequence.get(1);
    else if(sequence.get(1).equals(sequenceCurrentNum))
        return sequence.get(2);
    
    //This is not a finite loop, just for my testing i am running 300 iterations.       
    for(int i=0;i<300;i  ) {                    
        if(sequence.get(i).equals(sequenceCurrentNum)) {
            return sequence.get(i 1);
        }
        
        int nextVal = sequence.get(i)*10;
        
        Integer firstSeq = nextVal   sequence.get(0);
        Integer secondSeq = nextVal   sequence.get(1);
        Integer thirdSeq = nextVal   sequence.get(2);
        
        sequence.add(firstSeq);
        sequence.add(secondSeq);
        sequence.add(thirdSeq);     
        
        if(firstSeq.equals(sequenceCurrentNum)) {
            return secondSeq;               
        }else if(secondSeq.equals(sequenceCurrentNum)) {
            return thirdSeq;                
        }
    }       
    return 0;
}

My Approach:

I am constructing the entire sequence from the beginning

Then checking if we have reached to the given number in sequence.

Then return the successor.

Drawbacks:

I am constructing the entire sequence to reach to given number.

Memory wise and performance wise not suggestable.

Please help to understand, is there any better approach to get the successor without constructing entire sequence.

Example: Given 277755 should return 277757. (Without constructing the entire sequnce)

Note: The sequence will not be provided as an input to our function. The only input we will be given is a valid number from the sequence.

CodePudding user response：

Try this.

public static int getNextNumInSequence(Integer sequenceCurrentNum) {
    int head = sequenceCurrentNum / 10;
    int tail = sequenceCurrentNum % 10;
    int headNext = head == 0 ? 2 : getNextNumInSequence(head);
    if (headNext == 0) return 0;
    switch (tail) {
    case 2: return head * 10   5;
    case 5: return head * 10   7;
    case 7: return headNext * 10   2;
    default: return 0;
    }
}

public static void main(String[] args) {
    for (int i = 0, k = 2; i < 20;   i, k = getNextNumInSequence(k))
        System.out.println(i   " : "   k);
}

output:

You can also get n-th number.

public static int getNumAtIndex(int n) {
    int h = n / 3;
    int t = n % 3;
    return (h == 0 ? 0 : getNumAtIndex(h) * 10)
          (t == 0 ? 2 : t == 1 ? 5 : 7);
}

test:

public static void main(String[] args) {
    for (int i = 0; i < 10;   i)
        System.out.println(i   " : "   getNumAtIndex(i));
}

output:

CodePudding user response：

First try to understand what is the logic behind the sequence. If you look carefully to the numbers, you may see counting in ternary base. To be more clear, let's replace '2' by '0', '5' by '1' and '7' by '2'. Then your sequence becomes:

(0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, ...)

It's just counting. So the thing is to get the next number in ternary base, but using the digits 2, 5, 7. We must take care of digit 7: if we increment it, we get 2 but we have a carry for the digit before.

Here is a sample code:

public static Integer getNextNumInSequence(Integer number)
{
    int digits[] = {2,5,7};
    int idx_digits[] = {-1, -1, 0, -1, -1, 1, -1, 2, -1, -1};
    Integer next_number = 0;
    int carry = 1;
    Integer pow10 = 1;
    while (number>0)
    {
        int digit = number%10;      //extract last digit
        int idx_d = idx_digits[digit];      //get index of digit -- must be 0,1 or 2
        if (idx_d==-1)
        {
            System.out.println("Invalid number");
            return -1;
        }
        next_number  = digits[(idx_d carry)%3]*pow10;   //compute next digit in sequence, taking care of the carry
        carry = (digit==7)?1:0;     //carry is 1 only if the current digit is 7
        pow10 *= 10;            //increment 
        number /= 10;           //erase last digit
        if (carry==0)           //if no carry, we can stop the loop here, it's not useful to continue
        {
            break;
        }
    }
    // at this point, either number>0 or carry==1
    return ((carry>0)?2:number)*pow10 next_number;      //final number is the digit sequence [2 if carry else number ; next_number]
}

CodePudding user response：

To construct the list, you can simply do this:

    List<Integer> list = Arrays.asList(2, 5, 7, 22, 25, 27, 52, 55, 57, 72, 75, 77, 222);

Note that there are cases where there is not successor. Here I will return null in those cases:

public static Integer getNextNumInSequence(List<Integer> list, Integer num) {
    int pos = list.indexOf(num);
    if (pos >= 0 && pos 1 < list.size()) {
        return list.get(pos 1);
    }
    return null;
}

Note that I've added a parameter list so that you don't have to build the list each time you want to do a search.

In your example, the list is sorted; If it's always the case, you can use a binary search: Collections.binarySearch(list, num) instead of list.indexOf(num).

CodePudding user response：

OK. If I understand correctly, you have three initial values:

static final int[] initial = {2, 5, 7};

and you can calculate the value at position ix like this:

private static int calculate(int ix) {
    int div = ix/initial.length;
    int rest = ix%initial.length;
    int value = 0;
    if (div > 0) {
        value = 10*calculate(div-1);
    }
    return value initial[rest];
}

To get the successor of num:

public static Integer getNextNumInSequence(int num) {
    for (int i = 0; ;   i) {
        int cur = calculate(i);
        if (cur == num) {
            return calculate(i 1);
        } else if (cur > num) {
            return null;
        }
    }
}

CodePudding user response：

You can solve this recursively.

If the final digit of the given number is 2 or 5, then it is easy: just change that final digit to 5 or 7 respectively.

Otherwise (when the final digit is 7), solve the problem without the last digit, and then append the digit 2 to that result. Of course, "without last digit" means an integer division by 10, and "appending" means multiplying by 10 and then adding the value of the digit.

Here is the function:

public static int getNextNumInSequence(Integer curr) {
    if (curr % 10 == 2) return curr   3;
    if (curr % 10 == 5) return curr   2;
    if (curr == 7) return 22;
    return getNextNumInSequence(curr / 10) * 10   2;
}

Note that one call has worst case time complexity of O(logn) where n is the value of the function argument, but amortised time complexity is O(1) per call.