Palindrome Count

[shrutichandel]

A contest closes in n days hh hours, mm minutes and ss seconds. Given two values of n, how many palindromes of the format nhhmmss would we find in the indicated interval?

A string is said to be palindrome if it reads the same backwards as forwards.Here is what I tried,... would anyone please explain how should I proceed


#include<stdio.h>
int ifpalin(int g)
{
int rev=0;
int tmp=g;
while(tmp>0)
{
rev=rev*10+(tmp%10);
tmp=tmp/10;
}
if(rev==g)
return 1;
else
return 0;
}
int findpalin(int a1,int b1)
{
int sm=0;
for(int i=a1;i<=b1;i++)
{
if (ifpalin(i)==1)
sm++;
}
printf("%d",sm);
printf("\n");
return 0;
}
int main()
{
int a,b,n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a);
scanf("%d",&b);
findpalin(a,b);
}
return 0;
}

[jonnin]

compute them, don't seek them.

the real pattern here is
n1n2 mm n2n1

mm is 00,11,22,33,44,55 if we assume leading zeros.
so for every hour, in the interval, there at 6 palins, right?

given that you only have to deal with hours, is it literally (nn2-nn1)*6?
Or did I miss a pattern that needs to be counted?

[shrutichandel]

For further clarification read this


A contest closes in n days hh hours, mm minutes and ss seconds. Given two values of n, how many palindromes of the format nhhmmss would we find in the indicated interval?

A string is said to be palindrome if it reads the same backwards as forwards.

Constraints n2 - n1 <= 10

Input One line containing two integer n1 and n2, where n1< p="">

Output One integer representing the number of palindromes in this countdown interval

Time Limit 3

Examples Example 1

Input

1 2

Output

472

Explanation

We need to check the numbers 1000000 through 2235959 including only numbers where the last 6 digits correspond to times. We find 472 such numbers: 1000001, 1001001, 1002001, 1003001, 1004001, ..., 2231322, 2232322, 2233322, 2234322, 2235322

Example 2

Input

0 2

Output

708

Explanation

There are 708 palindromes: 0000000, 0001000, 0002000, 0003000, 0004000, ..., 2231322, 2232322, 2233322, 2234322, 2235322

[jonnin]

0000000 //this is a valid time? Is this a 24 hour clock?
I still think you can cook up a formula and get the count without a search/generate/count.
but I clearly missed all the single digit and internal pattern ones, have to find a way to determine those.
or at the very least, generate 000 to 999 table of true/false for whether it is both a valid palindrome and a valid time, use that lookup.

[shrutichandel]

@jonnin, you seem to be right that there might be some formula which I am missing.

[shrutichandel]

yes this is a 24-hr clock and I gave the example above... I thought that formula could be related to fact that for 0 and 1 as input it gives 236 (708-472) and for 1 & 2 answer is 472.

[shrutichandel]

@jonnin, any help. .. .

[jonnin]

yea you are all over it... its a pat answer depending on the hour.
I mean its fugly, but you can just find the answer for 00 to 23 and put that number in a table. Then you just sum those up over the hours you were given. It may turn out that there are only like 3 or 4 values depending on which hour it is. I dunno. Is this one of those idiot site problems where they want you to do a billion cases in a second?

[shrutichandel]

I didn't got what you want to say, would you please explain with code.

[shrutichandel]

@jonnin

[lastchance]

shrutichandel wrote:

Input
1 2

Output
472

Explanation
We need to check the numbers 1000000 through 2235959 including only numbers where the last 6 digits correspond to times. We find 472 such numbers: 1000001, 1001001, 1002001, 1003001, 1004001, ..., 2231322, 2232322, 2233322, 2234322, 2235322

I'm obviously missing something; I came up with
2 x 24 x 6
which is 288, not 472.

Can you explain the count and then maybe the logic will be clearer.

[jonnin]

I am not going to code it for you. You need to count them, though.
count how many you get in a 24 hour period. Then use the Ns to compute the answer.
the first example may just tell you: if you get 472 for 1, 2 then for 1, 3 you get twice that, right? Programs like this often have 2 programs: one to figure out part of the answer, like how many in an hour or 24 hours or whatever, and another that uses the result of the first to answer the bigger question quickly (once you know the magic number, you can just apply it in the second program, you don't need to find that again).

[againtry]

https://brainly.in/question/21009785

[jonnin]

I don't get 472 either. I stopped trying, I can't make sense of it. I get 6 per hour:
000, 010, 020, 030,040,050 //example for hour == 0
where these are the middle values:
NH hMm Ss
only hMm vary
M is from 0-5
m and h are equal and are 0-9
so 24 hours is 24*6 = 144 per day. I think this matches lastchance's approach.

[dhayden]

Let's assume a single digit for n. This is in direct conflict with the OP's statement:

Constraints n2 - n1 <= 10

Which would allow n2 = 12345677899 and n1 = 1234567895

Anyway, if n is a single digit then write the values like Jonnin did:
NHhMmSs

Separating into handy groups:
N Hh M mS s

So N matches s, Hh matches mS and M is in the middle.

N is however many days you're talking about and s can be any digit, so they always match

Hh is 00-23, but it must match mS and S can only be in the range 0-5. So there are 8 illegal values of Hh (06 07 08 09 16 17 18 19). Thus there are 24-8=16 legal values of Hh Edit: all values of Hh are legal, see Jonnin's post above and comment below.

M can be any value from 0-5.

So for each day there are 16*6=96 24*6=144 legal values and the full answer is N*96 N*144. This gives 192 288 palindromes for the first example (N=2) and 288 432 for the second example.

The full set for the first example. If the real answer is 472 then there should be plenty that I missed. Does anyone see any? Edit: see Jonnin's comment below

1:00:00:01 1:00:10:01 1:00:20:01 1:00:30:01 1:00:40:01 1:00:50:01
1:01:01:01 1:01:11:01 1:01:21:01 1:01:31:01 1:01:41:01 1:01:51:01
1:02:02:01 1:02:12:01 1:02:22:01 1:02:32:01 1:02:42:01 1:02:52:01
1:03:03:01 1:03:13:01 1:03:23:01 1:03:33:01 1:03:43:01 1:03:53:01
1:04:04:01 1:04:14:01 1:04:24:01 1:04:34:01 1:04:44:01 1:04:54:01
1:05:05:01 1:05:15:01 1:05:25:01 1:05:35:01 1:05:45:01 1:05:55:01
1:10:00:11 1:10:10:11 1:10:20:11 1:10:30:11 1:10:40:11 1:10:50:11
1:11:01:11 1:11:11:11 1:11:21:11 1:11:31:11 1:11:41:11 1:11:51:11
1:12:02:11 1:12:12:11 1:12:22:11 1:12:32:11 1:12:42:11 1:12:52:11
1:13:03:11 1:13:13:11 1:13:23:11 1:13:33:11 1:13:43:11 1:13:53:11
1:14:04:11 1:14:14:11 1:14:24:11 1:14:34:11 1:14:44:11 1:14:54:11
1:15:05:11 1:15:15:11 1:15:25:11 1:15:35:11 1:15:45:11 1:15:55:11
1:20:00:21 1:20:10:21 1:20:20:21 1:20:30:21 1:20:40:21 1:20:50:21
1:21:01:21 1:21:11:21 1:21:21:21 1:21:31:21 1:21:41:21 1:21:51:21
1:22:02:21 1:22:12:21 1:22:22:21 1:22:32:21 1:22:42:21 1:22:52:21
1:23:03:21 1:23:13:21 1:23:23:21 1:23:33:21 1:23:43:21 1:23:53:21
2:00:00:02 2:00:10:02 2:00:20:02 2:00:30:02 2:00:40:02 2:00:50:02
2:01:01:02 2:01:11:02 2:01:21:02 2:01:31:02 2:01:41:02 2:01:51:02
2:02:02:02 2:02:12:02 2:02:22:02 2:02:32:02 2:02:42:02 2:02:52:02
2:03:03:02 2:03:13:02 2:03:23:02 2:03:33:02 2:03:43:02 2:03:53:02
2:04:04:02 2:04:14:02 2:04:24:02 2:04:34:02 2:04:44:02 2:04:54:02
2:05:05:02 2:05:15:02 2:05:25:02 2:05:35:02 2:05:45:02 2:05:55:02
2:10:00:12 2:10:10:12 2:10:20:12 2:10:30:12 2:10:40:12 2:10:50:12
2:11:01:12 2:11:11:12 2:11:21:12 2:11:31:12 2:11:41:12 2:11:51:12
2:12:02:12 2:12:12:12 2:12:22:12 2:12:32:12 2:12:42:12 2:12:52:12
2:13:03:12 2:13:13:12 2:13:23:12 2:13:33:12 2:13:43:12 2:13:53:12
2:14:04:12 2:14:14:12 2:14:24:12 2:14:34:12 2:14:44:12 2:14:54:12
2:15:05:12 2:15:15:12 2:15:25:12 2:15:35:12 2:15:45:12 2:15:55:12
2:20:00:22 2:20:10:22 2:20:20:22 2:20:30:22 2:20:40:22 2:20:50:22
2:21:01:22 2:21:11:22 2:21:21:22 2:21:31:22 2:21:41:22 2:21:51:22
2:22:02:22 2:22:12:22 2:22:22:22 2:22:32:22 2:22:42:22 2:22:52:22
2:23:03:22 2:23:13:22 2:23:23:22 2:23:33:22 2:23:43:22 2:23:53:22

[jonnin]

All 24 hours are legal:
1:19:59:11
2:08:18:02

again as far as I can tell its the inner 3 digits that make the problem, and as far as I can tell, there are 6 / hour for all 24 hours?

[dhayden]

Thanks for the correction Jonnin. Here is the corrected output showing 288 values. Does anyone see missing palindromes here?

1:00:00:01 1:00:10:01 1:00:20:01 1:00:30:01 1:00:40:01 1:00:50:01
1:01:01:01 1:01:11:01 1:01:21:01 1:01:31:01 1:01:41:01 1:01:51:01
1:02:02:01 1:02:12:01 1:02:22:01 1:02:32:01 1:02:42:01 1:02:52:01
1:03:03:01 1:03:13:01 1:03:23:01 1:03:33:01 1:03:43:01 1:03:53:01
1:04:04:01 1:04:14:01 1:04:24:01 1:04:34:01 1:04:44:01 1:04:54:01
1:05:05:01 1:05:15:01 1:05:25:01 1:05:35:01 1:05:45:01 1:05:55:01
1:06:06:01 1:06:16:01 1:06:26:01 1:06:36:01 1:06:46:01 1:06:56:01
1:07:07:01 1:07:17:01 1:07:27:01 1:07:37:01 1:07:47:01 1:07:57:01
1:08:08:01 1:08:18:01 1:08:28:01 1:08:38:01 1:08:48:01 1:08:58:01
1:09:09:01 1:09:19:01 1:09:29:01 1:09:39:01 1:09:49:01 1:09:59:01
1:10:00:11 1:10:10:11 1:10:20:11 1:10:30:11 1:10:40:11 1:10:50:11
1:11:01:11 1:11:11:11 1:11:21:11 1:11:31:11 1:11:41:11 1:11:51:11
1:12:02:11 1:12:12:11 1:12:22:11 1:12:32:11 1:12:42:11 1:12:52:11
1:13:03:11 1:13:13:11 1:13:23:11 1:13:33:11 1:13:43:11 1:13:53:11
1:14:04:11 1:14:14:11 1:14:24:11 1:14:34:11 1:14:44:11 1:14:54:11
1:15:05:11 1:15:15:11 1:15:25:11 1:15:35:11 1:15:45:11 1:15:55:11
1:16:06:11 1:16:16:11 1:16:26:11 1:16:36:11 1:16:46:11 1:16:56:11
1:17:07:11 1:17:17:11 1:17:27:11 1:17:37:11 1:17:47:11 1:17:57:11
1:18:08:11 1:18:18:11 1:18:28:11 1:18:38:11 1:18:48:11 1:18:58:11
1:19:09:11 1:19:19:11 1:19:29:11 1:19:39:11 1:19:49:11 1:19:59:11
1:20:00:21 1:20:10:21 1:20:20:21 1:20:30:21 1:20:40:21 1:20:50:21
1:21:01:21 1:21:11:21 1:21:21:21 1:21:31:21 1:21:41:21 1:21:51:21
1:22:02:21 1:22:12:21 1:22:22:21 1:22:32:21 1:22:42:21 1:22:52:21
1:23:03:21 1:23:13:21 1:23:23:21 1:23:33:21 1:23:43:21 1:23:53:21
2:00:00:02 2:00:10:02 2:00:20:02 2:00:30:02 2:00:40:02 2:00:50:02
2:01:01:02 2:01:11:02 2:01:21:02 2:01:31:02 2:01:41:02 2:01:51:02
2:02:02:02 2:02:12:02 2:02:22:02 2:02:32:02 2:02:42:02 2:02:52:02
2:03:03:02 2:03:13:02 2:03:23:02 2:03:33:02 2:03:43:02 2:03:53:02
2:04:04:02 2:04:14:02 2:04:24:02 2:04:34:02 2:04:44:02 2:04:54:02
2:05:05:02 2:05:15:02 2:05:25:02 2:05:35:02 2:05:45:02 2:05:55:02
2:06:06:02 2:06:16:02 2:06:26:02 2:06:36:02 2:06:46:02 2:06:56:02
2:07:07:02 2:07:17:02 2:07:27:02 2:07:37:02 2:07:47:02 2:07:57:02
2:08:08:02 2:08:18:02 2:08:28:02 2:08:38:02 2:08:48:02 2:08:58:02
2:09:09:02 2:09:19:02 2:09:29:02 2:09:39:02 2:09:49:02 2:09:59:02
2:10:00:12 2:10:10:12 2:10:20:12 2:10:30:12 2:10:40:12 2:10:50:12
2:11:01:12 2:11:11:12 2:11:21:12 2:11:31:12 2:11:41:12 2:11:51:12
2:12:02:12 2:12:12:12 2:12:22:12 2:12:32:12 2:12:42:12 2:12:52:12
2:13:03:12 2:13:13:12 2:13:23:12 2:13:33:12 2:13:43:12 2:13:53:12
2:14:04:12 2:14:14:12 2:14:24:12 2:14:34:12 2:14:44:12 2:14:54:12
2:15:05:12 2:15:15:12 2:15:25:12 2:15:35:12 2:15:45:12 2:15:55:12
2:16:06:12 2:16:16:12 2:16:26:12 2:16:36:12 2:16:46:12 2:16:56:12
2:17:07:12 2:17:17:12 2:17:27:12 2:17:37:12 2:17:47:12 2:17:57:12
2:18:08:12 2:18:18:12 2:18:28:12 2:18:38:12 2:18:48:12 2:18:58:12
2:19:09:12 2:19:19:12 2:19:29:12 2:19:39:12 2:19:49:12 2:19:59:12
2:20:00:22 2:20:10:22 2:20:20:22 2:20:30:22 2:20:40:22 2:20:50:22
2:21:01:22 2:21:11:22 2:21:21:22 2:21:31:22 2:21:41:22 2:21:51:22
2:22:02:22 2:22:12:22 2:22:22:22 2:22:32:22 2:22:42:22 2:22:52:22
2:23:03:22 2:23:13:22 2:23:23:22 2:23:33:22 2:23:43:22 2:23:53:22

[jonnin]

thats what I get too. That is 3 of us with that answer now I believe.

[dhayden]

shrutichandel, it looks like the question is crap since it can't even get correct results for the examples. I'd move on to something else, preferably from a different site. Maybe pick some of the homework questions that have been posed here and see if you can do them.

Host of these "programming" sites are pretty useless for beginners because finding the algorithm is much harder than writing the code.

[againtry]

It's definitely 288 - ie 144 for any single digit prefix number entered.

#include <iostream>
#include <string>

bool isPalindrome(  std::string  aString )
{
      int i = 0, j = (int)aString.size() - 1;
  
      while ( i < j )
      {
          if ( aString[i] != aString[j])
              return false;
  
          i++;
          j--;
      }
      return true;
  }

int SECONDS{24*60*60};

int main()
{
    std::string tmp;
    int count{0};
    
    int hh{0}, mm{0}, ss{0};
    
    int a[2]{0};
    
    std::cout << "Enter two numbers: ";
    std::cin >> a[0] >> a[1];
    
    
    for(int j = 0; j < 2; ++j)
    {
        tmp = "";
        for (int i = 0; i < SECONDS; ++i)
        {
            ss = i % 60;
            mm = i / 60;
            
            hh = mm / 60;
            mm = mm % 60;
            
            tmp = std::to_string(a[j]);
            
            if(hh < 10){tmp += '0';}
            tmp += std::to_string(hh);
        
            if(mm < 10){tmp += '0';}
            tmp += std::to_string(mm);
            
            if(ss < 10){tmp += '0';}
            tmp += std::to_string(ss);
            
            if( isPalindrome(tmp) )
            {
                std::cout << tmp << '\n';
                count++;
            }
        }
    }
    std::cout << "Count: " << count << '\n';
    
    return 0;
}

Enter two numbers: 1 2
1000001
1001001
1002001
1003001
1004001
1005001
1010101
1011101
1012101
1013101
1014101
1015101
1020201
1021201
1022201
1023201
1024201
1025201
1030301
1031301
1032301
1033301
1034301
1035301
1040401
1041401
1042401
1043401
1044401
1045401
1050501
1051501
1052501
1053501
1054501
1055501
1060601
1061601
1062601
1063601
1064601
1065601
1070701
1071701
1072701
1073701
1074701
1075701
1080801
1081801
1082801
1083801
1084801
1085801
1090901
1091901
1092901
1093901
1094901
1095901
1100011
1101011
1102011
1103011
1104011
1105011
1110111
1111111
1112111
1113111
1114111
1115111
1120211
1121211
1122211
1123211
1124211
1125211
1130311
1131311
1132311
1133311
1134311
1135311
1140411
1141411
1142411
1143411
1144411
1145411
1150511
1151511
1152511
1153511
1154511
1155511
1160611
1161611
1162611
1163611
1164611
1165611
1170711
1171711
1172711
1173711
1174711
1175711
1180811
1181811
1182811
1183811
1184811
1185811
1190911
1191911
1192911
1193911
1194911
1195911
1200021
1201021
1202021
1203021
1204021
1205021
1210121
1211121
1212121
1213121
1214121
1215121
1220221
1221221
1222221
1223221
1224221
1225221
1230321
1231321
1232321
1233321
1234321
1235321
2000002
2001002
2002002
2003002
2004002
2005002
2010102
2011102
2012102
2013102
2014102
2015102
2020202
2021202
2022202
2023202
2024202
2025202
2030302
2031302
2032302
2033302
2034302
2035302
2040402
2041402
2042402
2043402
2044402
2045402
2050502
2051502
2052502
2053502
2054502
2055502
2060602
2061602
2062602
2063602
2064602
2065602
2070702
2071702
2072702
2073702
2074702
2075702
2080802
2081802
2082802
2083802
2084802
2085802
2090902
2091902
2092902
2093902
2094902
2095902
2100012
2101012
2102012
2103012
2104012
2105012
2110112
2111112
2112112
2113112
2114112
2115112
2120212
2121212
2122212
2123212
2124212
2125212
2130312
2131312
2132312
2133312
2134312
2135312
2140412
2141412
2142412
2143412
2144412
2145412
2150512
2151512
2152512
2153512
2154512
2155512
2160612
2161612
2162612
2163612
2164612
2165612
2170712
2171712
2172712
2173712
2174712
2175712
2180812
2181812
2182812
2183812
2184812
2185812
2190912
2191912
2192912
2193912
2194912
2195912
2200022
2201022
2202022
2203022
2204022
2205022
2210122
2211122
2212122
2213122
2214122
2215122
2220222
2221222
2222222
2223222
2224222
2225222
2230322
2231322
2232322
2233322
2234322
2235322
Count: 288
Program ended with exit code: 0