Array find value using index logic interview questions

Question

Below is given array for infinite length which has natural numbers as it can be infinite length:

int[] myArray = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3 ......}; 

// at place of 10 it'll take 1, 0, at place of 11 it'll take 1, 1, at place of 12 it'll take 1, 2 an so on.....

index 0 = >  value 0 = >  number 0
index 1 = >  value 1 = >  number 1
index 2 = >  value 2 = >  number 2
index 3 = >  value 3 = >  number 3
index 4 = >  value 4 = >  number 4
index 5 = >  value 5 = >  number 5
index 6 = >  value 6 = >  number 6
index 7 = >  value 7 = >  number 7
index 8 = >  value 8 = >  number 8
index 9 = >  value 9 = >  number 9
index 10 = > value 1 = > number 10
index 11 = > value 0 = > number 10
index 12 = > value 1 = > number 11
index 13 = > value 1 = > number 11
index 14 = > value 1 = > number 12
index 15 = > value 2 = > number 12

....
....
....

for index 9 value should be 9, but at index 10 instead of value as 10 it should be 1 & again at index 11 value should be 0 , then at index 12 value should be 1 and so on...

Suppose for index value 10 we get a result as 1, for value 11 we get a result value as 0.

We have to write our logic to get the value by passing index value, index can be from 0 to 10000000.

We can not directly use array to get the value at specific index, we have to write logic like below:

public int getValue(int index){

    int value = 0;

    //  logic to find the the value 

    return value;
}

I have tried below approach to get the result for passed index, but it works till two digits numbers i.e. 99. (till index 189). But for three digits & further we have to change the logic.

public static int myMethod(int index){
    System.out.println("index : " + index);

    if(index <= 9){
        return index;
    }

    boolean even = (index % 2) == 0;

    int num = 0 ;
    char res = 0;
    if(even){
        num = index - ((index - 10) / 2);
        System.out.println("num " + num);

        res = new Integer(num).toString().charAt(0);            
    }else{

        index = index -1;
        num = index - ((index - 10) / 2);
        System.out.println("num 22 : " + num);
        res = new Integer(num).toString().charAt(1);            
    }

    int result = new Integer(res+"");

    System.out.println(result);
    return result ;
}

Answer 1

I'm going to say we start from 1 instead of 0 to make the below simpler (you can just subtract 1 from the index to include it).

Let's start with some analysis:

• There are 9 1-digit numbers (1-9) consuming the first 9*1 = 9*10⁰*1 = 9 positions.
• There are 90 2-digit numbers (10-99) consuming the next 90*2 = 9*10¹*2 = 180 positions.
• There are 900 3-digit numbers (100-999) consuming the next 900*3 = 9*10²*3 = 2700 positions.
• Etc.

As can be seen from the above, the n-digit numbers take up 9*10^n-1*n positions.

From here, it's not too hard to convert an index to the corresponding number by:

• Looping over each of the above cases (with a simple for loop), subtracting the corresponding number of positions from our index until doing this would give us a negative number.
• Divide our index by the number of digits we're currently at to get the offset, then add the first value using that number of digits (which is a multiple of 10) to find the number we're looking for.
• To determine the digit we're looking for (if not looking for the whole number), we can take the remainder of our the above division to give us our answer.

For example:

• Let's say we need to get the value of index 200 (or 201, if starting from 0).
• Excluding the 1-digit numbers gives us 200-9 = 191.
• Excluding the 2-digit numbers gives us 191-180 = 11.
• Trying to exclude the 3-digit numbers would lead to a negative number, so we know it's a 3-digit number.
• Divide 11 by the number of digits (3) to give us 3 (rounded down).
• The 3rd (starting from 0) 3-digit number is 100+3 = 103.
• Since 11%3 = 2, we're looking for the 2nd digit (starting from 0), so 3 is our answer.

Code:

final int[] POWERS_OF_10 = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
int getValue(int index){
    if (index-- == 0) // remove this if-statement to start from 1
        return 0;
    int digits = 0;
    int positions = 0;
    while (positions <= index)
    {
        index -= positions;
        digits++;
        positions = 9 * digits * POWERS_OF_10[digits-1];
    }
    int number = index / digits + POWERS_OF_10[digits-1];
    int digit = index % digits;
    int value = Integer.toString(number).charAt(digit) - '0'; // lazy approach
    // int value = number / POWERS_OF_10[digits-digit-1] % 10; // non-lazy approach
    return value;
}

This:

for (int i = 0; i < 20; i++)
    System.out.print(getValue(i) + ", ");

Will print out:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 

Live demo.

Answer 2

This sequence is known as the Champernowne constant.

The basic approach is to work out how the total length of all the 1 digit, 2 digit, 3 digit numbers, etc. Once you know which digit range is appropriate, you can identify the exact number within the range, and then the exact digit within the number.

Full details of an efficient algorithm can be found in this pdf.

Answer 3

This function (in JavaScript convert it yourself to Java), gives for an index x the length of the number and the position of the digit under this index.

Eg. For index 15, it wil return {length: 2, pos: 1} because under index 15 there is the 2 of 12, so the index of 2 relative to 12 is 1 and the length of 12 is 2 digits.

index: 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|..
value: 0|1|2|3|4|5|6|7|8|9|1 |0 |1 |1 |1 |2 |..

I guess that you can write the code to grab the right values from the array yourself.

function find(x){
  var length = 0;
  while(x > 0){
    length++;
    x = x - (10**(length-1)) * length * 9;
  }
  return {length: length, pos: (x % length) + length -1};
}

console.log(find(15));