ຕົວລະຄອນທີ N ໃນສາຍ ສຳ ລັບເລກປະເພນີ Concatenated  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Oracle
string

ຖະແຫຼງການບັນຫາ  

ໃນ“ ຕົວລະຄອນທີ N ໃນຕົວເລກ Concatenated Decimal String” ພວກເຮົາໄດ້ໃຫ້ຄ່າຕົວເລກ“ n”. ຂຽນໂປຼແກຼມເພື່ອຊອກຫາຕົວອັກສອນ Nth ໃນສາຍທີ່ອັດຕານິຍົມທັງ ໝົດ ຖືກສະຫຼຸບ.

ຮູບແບບການປ້ອນຂໍ້ມູນ  

ເສັ້ນ ທຳ ອິດແລະພຽງເສັ້ນດຽວທີ່ມີຄຸນຄ່າຂອງເລກເຕັມ n.

ຮູບແບບຜົນໄດ້ຮັບ  

ພິມຕົວ ໜັງ ສືຢູ່ ຕຳ ແໜ່ງ“ n” ໃນ string ເຊິ່ງອັດຕານິຍົມທັງ ໝົດ ຖືກສະຫຼຸບລົງ.

ຂໍ້ ຈຳ ກັດ  

  • 1 <= n <= 10 ^ 5

ຍົກຕົວຢ່າງ  

7
7

ຄໍາອະທິບາຍ: ໃຫ້ປະກອບເປັນສາຍເຊືອກທີ່ຄວາມຍາວຂອງມັນແມ່ນ 7 ແລະອັດຕານິຍົມທັງ ໝົດ ຈະຖືກຂັງໄວ້ໃນນັ້ນ. ສະນັ້ນ, ສະຕິງຂອງພວກເຮົາແມ່ນ“ 1234567”. ຕອນນີ້ພວກເຮົາກວດເບິ່ງຕົວລະຄອນທີ 7 ໃນສາຍເຊັກເຊິ່ງແມ່ນ 7. ສະນັ້ນ ຄຳ ຕອບສຸດທ້າຍຂອງພວກເຮົາແມ່ນ“ 7”.

10
1

ຄໍາອະທິບາຍ: ໃຫ້ປະກອບເປັນສະຕິງທີ່ concatenate 10 ຕົວເລກ. ສະນັ້ນ, ສະຕິງຂອງພວກເຮົາແມ່ນ“ 12345678910”. ຕອນນີ້ພວກເຮົາກວດເບິ່ງຕົວອັກສອນທີ 10 ໃນສາຍເຊັກຊຶ່ງເປັນ 1. ດັ່ງນັ້ນ ຄຳ ຕອບສຸດທ້າຍຂອງພວກເຮົາແມ່ນ“ 1”.

ວິທີການ  

ໃນວິທີການນີ້ແນວຄວາມຄິດຕົ້ນຕໍແມ່ນ, ພິຈາລະນາຄວາມຈິງທີ່ວ່າໃນອັດຕານິຍົມ 9 ຕົວເລກມີຄວາມຍາວ 1, 90 ຕົວເລກມີຄວາມຍາວ 2 ແລະ 900 ຕົວເລກມີຄວາມຍາວ 3 ແລະອື່ນໆ. ສະນັ້ນຂ້າມຕົວເລກເຫລົ່ານີ້ຕາມ N ທີ່ລະບຸແລະຊອກຫາຕົວລະຄອນ

1. ຊອກຫາຄວາມຍາວຂອງເລກທີ່ N

2. ດຽວນີ້, ຮັບຕົວລະຄອນທີ່ N

ເບິ່ງ
ສູດການຄິດໄລ່ Rabin Karp

ຍົກຕົວຢ່າງ

N = 51

1) ຊອກຫາຄວາມຍາວຂອງເລກທີ່ N
51 - 9 = 42 // ມີ 9 ຕົວເລກທີ່ມີຄວາມຍາວ 1
42 - 90 * 2 <0 // ຍ້ອນວ່າມີ 90 ຕົວເລກທີ່ມີຄວາມຍາວ 2, ພວກເຮົາຕ້ອງຮູ້ວ່າຄວາມຍາວແມ່ນ 2

2) ຊອກຫາຕົວລະຄອນທີ່ N
42 ຕົວອັກສອນແມ່ນຫຼັງຈາກທີ່ມີຕົວເລກສູງສຸດ 1 ຕົວເລກ (ຕົວເລກ 9)
ceil (42/2) = 21, ດັ່ງນັ້ນ 9 + 21 = 30. ສະນັ້ນ, 30 ແມ່ນ ໝາຍ ເລກທີ່ N.
ດຽວນີ້, ຊອກຫາຕົວລະຄອນຕົວຈິງຢູ່ທີ່ N
42% 2 = 0, ສະນັ້ນເອົາຕົວເລກທີ 2 ຂອງ 30. ສະນັ້ນ, 0 ແມ່ນຕົວລະຄອນທີ່ N

ການປະຕິບັດ  

ໂປຣແກຣມ C ++ ສຳ ລັບ Nth Character ໃນ Concatenated Decimal String

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
  int n;
  cin>>n;
  int sum=0,nine=9,dist=0,len; 
  for(len=1; ;len++) 
  { 
    sum+=nine*len;
    dist+=nine; 
    if(sum>=n) 
    { 
      sum-=nine*len; 
      dist-=nine; 
      n-=sum; 
      break; 
    } 
    nine*=10; 
  } 
  int diff=ceil((double)n/len); 
  int d=n%len; 
  if(d==0)
  {
    d=len;
  }
  n=dist+diff;
  string str; 
  stringstream ss; 
  ss<<n; 
  ss>>str; 
  cout<<str[d - 1]<<endl; 
  return 0; 
} 

ໂປແກຼມ Java ສຳ ລັບຕົວອັກສອນ Nth ໃນ Concatenated Decimal String

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                int n=sr.nextInt();
                int sum=0,nine=9,dist=0,len;   
                for(len=1; ;len++)  
                {  
                    sum+=nine * len;  
                    dist+=nine;  
                    if(sum>=n)  
                    {   
                        sum-=nine*len;  
                        dist-=nine;  
                        n-=sum;  
                        break;  
                    }  
                    nine*=10;  
                }    
                int diff=(int)(Math.ceil((double)(n)/(double)(len)));  
                int d=n%len;  
                if(d==0)  
                {
                    d=len;
                }  
                String str=Integer.toString(dist+diff); 
                System.out.println(str.charAt(d-1)); 
  } 
} 
51

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບຕົວລະຄອນທີ N ໃນຕົວເລກ Concatenated Decimal String  

ຄວາມສັບສົນເວລາ

O (Log N) ບ່ອນທີ່ N ແມ່ນເລກເຕັມໃຫ້. ນີ້ແມ່ນພື້ນຖານຂອງໄມ້ທ່ອນແມ່ນ 10.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ໄດ້ໃຊ້ບ່ອນພິເສດຢູ່ບ່ອນນີ້. ພວກເຮົາພຽງແຕ່ຊອກຫາ ຄຳ ຕອບໂດຍໃຊ້ການ ດຳ ເນີນງານ ຈຳ ນວນ ໜຶ່ງ ໂດຍໃຊ້ຕົວແປ ຈຳ ນວນ ໜຶ່ງ.