Find heavy integers
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (4767)

You are given two non negative integers A and B . How will you find the number of heavy integers in the interval [ A,B ] ( A , B inclusive).


Posted Answers

A non-negative integer is called heavy if the average value of its digits in decimal representation is greater than 7 . Example : 9868 is a heavy integer since the average of its digit is (9+8+6+8) = 7.75 .

To find the number of heavy integers between two given non negative integers we can skip the numbers having average less than 7 and increment the number from the units place to bring the average value over 7 . For that we calculate the sum of digits and the number of digits, but not the average. For a heavy number, \( \frac{Sum\ of\ digits}{Number\ of\ digits}>7 \). So we skip the number when \( \frac{Sum\ of\ digits}{Number\ of\ digits}\leq7 \) and need minimum, lets call it difference sum, \( (7 \times Number\ of\ digits)-Sum\ of\ digits+1 \) to bring the average above 7 .

Example - If the number is 53141 ; Sum of digits=14 , Number of digits=5 . Difference sum is (7*5)-14+1 = 22 . So, we will increment 53141 by 25555 , where 2+5+5+5+5=22 , to 78696 , which is a heavy number (\( \frac{7+8+6+9+6}{5}=7.2 \)).

public static int[] findHeavyInteger(int a, int b){

/* create an empty array to store the heavy integers between a & b */
List heavyIntArray = new ArrayList ();

/* Variables */
/* Sum of all digits of an element */
int actualSumOfDigits;
/* Sum of digits required to become an heavy integer */
int targetSumOfDigits;
/* Number of digits in an element */
int numberOfDigits;

while (a < = b){

actualSumOfDigits = 0;
numberOfDigits = 0;
int i = a;

/* Calculate number of digits and sum of digits */
while (i != 0){
actualSumOfDigits += i % 10;
numberOfDigits++;
i /= 10;
}

/* Calculate Target Sum */
targetSumOfDigits = 7 * numberOfDigits + 1;

/* Compare actualSumOfDigits and targetSumOfDigits */
/* Difference sum found: Not heavy integer : If actualSumOfDigits is
less than targetSumOfDigits*/
if (actualSumOfDigits < targetSumOfDigits)
a += computeIncrement(a, targetSumOfDigits - actualSumOfDigits);

/* Heavy integer */
else{
heavyIntArray.add(a);
a++;
}
return heavyIntArray;
}

}

public int computeIncrement(int num, int differenceSum) {

/* Variables */
int increment = 0;
int d = 1;
%int t = num;
int dv = 0;

/* When differenceSum is found : NOT heavy integer */
while (differenceSum > 0) {
dv = num % 10;
if (dv < 9){
final int incrementD = dv < differenceSum ? 9 - dv : differenceSum;
increment += incrementD * d;
differenceSum -= incrementD;
increment += differenceSum < 0 ? differenceSum * d : 0;
}
d *= 10;
num /= 10;
}
return increment;
}

You need to Sign In to post your solution.