fork(1) download
copy 
  1. /***********************************************************************
  2. Problem: Numbers are serialized increasingly into a sequence in the format 
  3. of 0123456789101112131415..., which each digit occupies a position in the 
  4. sequence. For instance, the digit in the position 5 is 5, in the position 
  5. 13 is 1, in the position 19 is 4, and so on.
  6.  
  7. Please write a function/method to get the digit on any given position.
  8. ***********************************************************************/
  9.  
  10. #include <iostream>
  11.  
  12. using namespace std;
  13.  
  14. int countOfIntegers(int digits);
  15. int digitAtIndex(int index, int digits);
  16. int beginNumber(int digits);
  17.  
  18.  
  19. int digitAtIndex(int index)
  20. {
  21.     if(index < 0)
  22.         return -1;
  23.  
  24.  
  25.     int digits = 1;
  26.     while(true)
  27.     {
  28.         int numbers = countOfIntegers(digits);
  29.         if(index < numbers * digits)
  30.             return digitAtIndex(index, digits);
  31.  
  32.  
  33.         index -= digits * numbers;
  34.         digits++;
  35.     }
  36.     return -1;
  37. }
  38.  
  39. int countOfIntegers(int digits)
  40. {
  41.     if(digits == 1)
  42.         return 10;
  43.  
  44.  
  45.     int count = 1;
  46.     for(int i = 1; i < digits; ++i)
  47.         count *= 10;
  48.     return 9 * count;
  49. }
  50.  
  51. int digitAtIndex(int index, int digits)
  52. {
  53.     int number = beginNumber(digits) + index / digits;
  54.     int indexFromRight = digits - index % digits;
  55.     for(int i = 1; i < indexFromRight; ++i)
  56.         number /= 10;
  57.     return number % 10;
  58. }
  59.  
  60. int beginNumber(int digits)
  61. {
  62.     if(digits == 1)
  63.         return 0;
  64.  
  65.  
  66.     int begin = 1;
  67.     for(int i = 1; i < digits; ++i)
  68.         begin *= 10;
  69.     return begin;
  70. }
  71.  
  72. //================================= Test Code =================================
  73. void test( char* testName, int inputIndex, int expectedOutput)
  74. {
  75.     if(digitAtIndex(inputIndex) == expectedOutput)
  76.         cout << testName << " passed." << endl;
  77.     else
  78.         cout << testName << " FAILED." << endl;
  79. }
  80.  
  81.  
  82. int main()
  83. {
  84.     test("Test1", 0, 0);
  85.     test("Test2", 1, 1);
  86.     test("Test3", 9, 9);
  87.     test("Test4", 10, 1);
  88.     test("Test5", 189, 9); // last digit of 99
  89.     test("Test6", 190, 1); // first digit of 100
  90.     test("Test7", 1000, 3); // first digit of 370
  91.     test("Test8", 1001, 7); // middle digit of 370
  92.     test("Test9", 1002, 0); // last digit of 370
  93.     return 0;
  94. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test1 passed.
Test2 passed.
Test3 passed.
Test4 passed.
Test5 passed.
Test6 passed.
Test7 passed.
Test8 passed.
Test9 passed.
https://ideone.com/yogYbu
Digits in a Sequence
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!