import java.util.*; /* * Given two numbers f and t, find the number of zeros in all numbers between f and t. * there are two functions that compute that: countZeros and countZerosFast5. Both have * the same idea. Both functions assume that f and t has the same number of digits. * Notice that iterating thru all numbers in between and counting zeros is * not a fisible solution. * * test and testRandom: these method tests the solution. * solution sketch * example: f = 121 t = 432 * ------------------------------ * n = (how many digit f has) = 3 * * 1. find number of zero in the right most location of all numbers * diff = t - f + 1 = 312 * For sure we will have 312/10 = 31.2 = 31 zeros * f = f /10= 12 * t = t/10 =43 * 2. find the number of zeros in the second location from right * diff = t -f + 1 =22 * so we will have 22/10 = 2.2 ==> 2 * 10 = 20 zeros * 3 .... * * The problem arises in the following cases: * problem 1. what to do with fraction: e.g. 31.2 should we consider one more zero or not? * s1. Only if the from_digit > to_digit. For example if we have * f = 125 t = 431 * diff = 317 / 10 = 31.7 since 5 > 1 (right most digit) then * number of zeros = 31 + 1 = 32 zeros. * problem 2: what if the first digit is zero, (in the from number) * s2. example: f = 102 t = 433 (compute how many zero in the second location) * diff = 43 - 10 + 1 = 34 --> 34/10 = 3.4 hence we will have for sure 3*10 zeros * but for the fist digit we won't have 10 zeros instead we will have only 4 zeros * number of zeros = 30 + 4 = 34 (notice that you need to keep track with all right * most digits before the one you're processing) * problem 3. what if the second digit is zero, (in the to number) * s2. example: f = 142 t = 403 (compute how many zero in the second location) * diff = 40 - 14 + 1 = 27 --> 27/10 = 2.7 hence we will have for sure 2*10 zeros * but for the second digit we won't have 10 zeros instead we will have only 4 zeros * number of zeros = 20 + 4 = 24 (notice that you need to keep track with all right * most digits before the one you're processing) * Problem 4. what if both numbers have zero in the same rank * combine 2 and 3 for solution. * */ public class ManyO { public static void main(String[] args){ String input = "120 130\n"+ "10 11\n" + "100 200\n" + "0 500\n"+ "173 390\n"+ "1234567890 2345678901\n"+ "0 4294967295\n"; String output = "1\n22\n92\n987654304\n3825876150"; Scanner s = new Scanner( input); while(s.hasNextLine()){ String[] line = s.nextLine().split(" "); long from = Long.parseLong(line[0]); long to = Long.parseLong(line[1]); System.out.println(countZerosInRange(from,to)); } } static void testRandom(){ Random r = new Random( System.currentTimeMillis()); int MAG = 10000; for(int i=0;i<100000;i++){ long l1 = (long) r.nextInt(MAG); long l2 = r.nextInt(MAG); if(intSize(l1) != intSize(l2)) { i--; continue; } if(l1 > l2){ long t = l1; l1 = l2; l2 = t; } int x = (int)countZeros3(l1,l2); //int y = (int)countZerosFast5(l1,l2); int y = (int) countZeros(l1,l2); if(x != y){ System.err.println(l1 +" , " + l2 + " ==> x =" + x + " , y =" + y); System.exit(0); }else{ System.out.println(x + "==>" + y); } } } static void test(){ Scanner s = new Scanner(System.in); System.err.print("enter n1>>"); while( s.hasNext() ){ long n1 = s.nextLong(); System.err.print("enter n2>>"); long n2 = s.nextLong(); System.err.println(countZeros3(n1,n2) +"-->" + countZeros(n1,n2)); System.err.print("enter n1>>"); } } public static int intSize(long l){ return ("" + l).length(); } public static long countZeros3(long f, long t){ long l = 0; while( f <= t){ String s = f +""; for(int x = 0;x to) { _to = to; flag = true; } //long xx = countZerosFast5(_from,_to); long xx = countZeros(_from,_to); total += xx; _from = _to + 1; fSize = intSize(_from); } return total; } /* * count how many zeros in the numbers between ff and tt asuming that * both ff and tt has the same number of digits. */ public static long countZerosFast5(long ff, long tt){ int l = intSize(ff); long from_rmn = 0; long to_rmn = 0; long total = 0; for(int i=0;i t_rmd) mul++; total += mul * x; }else if(isFromZero && !isToZero){ if(hasRemainder){ total += mul * x; }else total += (mul - 1) * x; if(from_rmn == 0) total+= x; else total += (x - from_rmn); }else if(!isFromZero && isToZero){ if(hasRemainder){ total += mul * x; }else total += (mul - 1) * x; if(to_rmn == 0) total+= 1; else total += to_rmn + 1; }else{ if(hasRemainder){ total += (mul-1) * x; }else total += (mul - 2) * x; if(from_rmn == 0) total+= x; else total += (x - from_rmn); if(to_rmn == 0) total+= 1; else total += to_rmn + 1; } from_rmn += f_rmd * x; to_rmn += t_rmd * x; //System.out.println("total:" + total); ff = ff / 10; tt = tt / 10; } return total; } /* * count how many zeros in the numbers between ff and tt asuming that * both ff and tt has the same number of digits. */ public static long countZeros(long ff, long tt){ int l = intSize(ff); long from_rmn = 0; long to_rmn = 0; long total = 0; long ptotal =0; for(int i=0;i t_rmd) mul++; } total += mul * x; // problems appears only if there is an upper zero, lower zero // or both in that case we must have overcounted, so we need to // subtract if(isFromZero){ if(hasRemainder){ total+= x; } if(from_rmn !=0){ total -= from_rmn; } } if(isToZero){ long yy = x -1; if(to_rmn != 0) yy = x - to_rmn -1 ; total -= yy; } from_rmn += f_rmd * x; to_rmn += t_rmd * x; ptotal = total; ff = ff / 10; tt = tt / 10; } return total; } }