The algorithm is necessary

[XCHG]

Hi
There are two numbers N and M ( 0 < M, N < 10^100).
How many numbers encounter at the decimal representation number M not more than N?
The algorithm is very necessary for me =/

[bilm_ks]

I think you must make it more clear. You know somehow N and M iterates from 1 to 10^100 - 1?

[RoboTact]

Clarify 'encounter'. Does it mean being substring? That is with N=121, M=2, there are 2 encounters of 1 (being not more then M=2) and one encounter of 2 (being not more then M=2), and answer is 3.

[XCHG]

For example:
N=122, m = 12:
The answer is 4:
12, 120, 121, 122

N=99, m = 1:
The answer is 19:
1, 10, 11, 12, 13..., 21, 31, 41, 51 ... 91

[dglienna]

Didn't you miss 112 in the first example? :D

Something like this should do what you want. Tested, and ironed out a bug.

Option Explicit

Private Sub Form_Activate()
Dim a As Integer
Dim b As Integer
a = InputBox("Enter Number of Items")
b = InputBox("Enter Number to find")
Call FindIt(b, a)
End Sub

Sub FindIt(n As Integer, m As Integer)
Dim x As Integer
Dim p As Integer
Dim t As String
Dim ct As Integer
Dim str As String
t = CStr(n)
For x = 1 To m
p = InStr(CStr(x), t)
If p > 0 Then
str = str & CStr(x) & ","
ct = ct + 1
End If
Next x
str = Left$(str, Len(str) - 1) & vbCrLf
str = str & n & " occurrs " & ct & " times"
MsgBox str
End Sub


Decided after the fact to make it a subroutine, so that you could call as needed.

EDIT: Hope you're using VB6 :)

[XCHG]

Didn't you miss 112 in the first example? :D:)
Yes, of course! :)


Something like this should do what you want. Tested, and ironed out a bug.

Option Explicit

Private Sub Form_Activate()
Dim a As Integer
Dim b As Integer
a = InputBox("Enter Number of Items")
b = InputBox("Enter Number to find")
Call FindIt(b, a)
End Sub

Sub FindIt(n As Integer, m As Integer)
Dim x As Integer
Dim p As Integer
Dim t As String
Dim ct As Integer
Dim str As String
t = CStr(n)
For x = 1 To m
p = InStr(CStr(x), t)
If p > 0 Then
str = str & CStr(x) & ","
ct = ct + 1
End If
Next x
str = Left$(str, Len(str) - 1) & vbCrLf
str = str & n & " occurrs " & ct & " times"
MsgBox str
End Sub


Decided after the fact to make it a subroutine, so that you could call as needed.

EDIT: Hope you're using VB6 :)
Thanks for help!But it seems to me the artful algorithm here is necessary

[bilm_ks]

if N = 23124...56443 with n digits and M = 34...4 with m digits we are moving M over N in all possible positions that can be appear (there are n-m+1 positions). In such a position there are l*r numbers that contain the M.
For example for N = 24586 and M = 23 moving M at the third digit of N we get 24[23]6 so for this position we have 25*10 numbers containing 23. 25 stands for 24+1(24 plus zero) 10 stands for the combinations of the digits on the right. There is one digit so 10^1 = 10. As you can see in this case 23 is smaller of 58(which is replaced) so the above calculation is correct. If I had N = 24106 now 23>10 so I ll never have 2423d. I must mul with 24 now(one less) to be correct : 24*10. Another situation is N = 24236 so 23 = 23. In this case i can have 2423d but on the right i cant get all 10 combinations because for 2423d d is up to 6. So i must take 24*10 (all combinations up to 23[23]6 plus 7 (6 plus zero). This is how the below code works

// power of ten
unsigned __int64 Pow10(unsigned int exp)
{
if (exp == 0) return 1;
unsigned __int64 res = 10;
for (int i = 2; i <= exp; i++)
{
res *= 10;
}
return res;
}

unsigned __int64 NumOfInst(int * pBig, int nBigSize, int * pSmall, int nSmallSize)
{
unsigned __int64 res = 0;
unsigned __int64 leftnum, rightnum, rightmul;
int rightdig, count, n;
bool bigSmall, bEqual;
// moving small from left to right
for (int i = 0; i <= nBigSize - nSmallSize; i++)
{
rightdig = nBigSize - i - nSmallSize;
leftnum = rightnum = 0;
n = 0;
// find left num
for (count = i - 1; count >= 0; count--)
leftnum += pBig[count]*Pow10(n++);
leftnum++; // incr to include zero
// find right num
n = rightdig - 1;
for (count = i + nSmallSize; count < nBigSize; count++)
rightnum += pBig[count]*Pow10(n--);
rightnum++; // incr to include zero
// find right mul
rightmul = Pow10(rightdig);
// Compare small with corresponding big digs
bEqual = true;
for (count = 0; count < nSmallSize; count++)
{
if (pSmall[count] > pBig[count + i]) {
bigSmall = true;
bEqual = false;
break;
}
else if (pSmall[count] < pBig[count + i]) {
bigSmall = false;
bEqual = false;
break;
}
}
if (bEqual) // all left valid, right up to the rightnum
res += (leftnum - 1) * rightmul + rightnum;
else if (bigSmall) // leftnum - 1, right 10^(digs)
res += (leftnum - 1) * rightmul;
else // all left valid
res += leftnum * rightmul;
}
return res;
}

int _tmain(int argc, _TCHAR* argv[])
{
int nBig, nSmall;
int *pBig, *pSmall;
unsigned __int64 res;
printf("\nEnter number of digits for the big number : ");
fflush(stdin);
scanf("%d", &nBig);
pBig = new int[nBig];
printf("\nEnter digits of the big number\n\n");
for (int i = 0; i < nBig; i++)
{
printf("Enter digit %d : ", i + 1);
fflush(stdin);
scanf("%d", &pBig[i]);
}
printf("\nEnter number of digits for the small number : ");
fflush(stdin);
scanf("%d", &nSmall);
pSmall = new int[nSmall];
printf("\nEnter digits of the small number\n\n");
for (int i = 0; i < nSmall; i++)
{
printf("Enter digit %d : ", i + 1);
fflush(stdin);
scanf("%d", &pSmall[i]);
}
res = NumOfInst(pBig, nBig, pSmall, nSmall);
printf("\n\nThere are %I64u instances\n\n", res);
return 0;
}


oops forgot to delete the arrays (never mind) :)

[RoboTact]

Test it with big=11 and small=1.
You count the same number multiple times, as small may be substring of big in more then one place.

[XCHG]

2bilm_ks:
You great! Thanks a lot

[XCHG]

But I don't understand how it works! (
Where i can get more info(Links, Section of mathematics)?

[RoboTact]

Again - solution is wrong. How urgent is it? I feel too lazy to solve it...

[bilm_ks]

This counts all instances of number M in all numbers up to N. (Not just the numbers that contain number M). If this is what you want ok. Otherwise multiple instances must removed. I ll check it again sometime. As for the "how" is more common sence rather than mathematics. Check for combinations if you are interesting about something relative.

[dglienna]

I don't think you'd be able to get an algorithm that would return the desired result. That's why I suggested a string approach, which would be a lot faster.