Coding Problem 7: Techfest and the Queue [GFG - Problem Solving]

By -

 

A Techfest is underway, and each participant is given a ticket with a unique number. Organizers decide to award prize points to everyone who has a ticket ID between a and b (inclusive). The points given to a participant with ticket number x will be the sum of powers of the prime factors of x.

For instance, if points are to be awarded to a participant with ticket number 12, the amount of points given out will be equal to the sum of powers in the prime factorization of 12 (22 × 31), which will be 2 + 1 = 3.

Given a and b, determine the sum of all the points that will be awarded to the participants with ticket numbers between a and b (inclusive).

Example 1:

Input: 
a = 9
b = 12
Output: 
8
Explanation: 
For 9, prime factorization is:32 
So, sum of the powers of primes is: 2
For 10, prime factorization is : 21x51 
So, sum of the powers of primes is: 2
For 11, prime factorization is : 111 
So, sum of the powers of primes is: 1
For 12, prime factorization is : 22x 31 
So, sum of powers of primes is: 3
Therefore the total sum is 2+2+1+3=8.

Example 2:

Input: 
a = 24, b = 27
Output: 
11
Explanation: 
For 24, prime factorization is: 23x31 
So, sum of the powers of primes is: 4
For 25, prime factorization is : 52 
So, sum of the powers of primes is: 2
For 26, prime factorization is : 131x21 
So, sum of the powers of primes is: 2
For 27, prime factorization is : 33  
So, sum of powers of primes is: 3
Therefore the total sum is 4+2+2+3=11.

Your Task:
You don't need to read or print anything. Your task is to complete the function sumOfPowers() which takes a and b as input parameters and returns the sum of the power of primes that occur in prime factorization of the numbers between a to b (inclusive).

Expected Time Complexity: O( b*log(b) )
Expected Space Complexity: O( b*log(b) )

Constraints:
1 <= a <= b <= 2x105
1 <= b-a <= 105

https://www.geeksforgeeks.org/problems/techfest-and-the-queue1044/1


Solution :

package com.coding.problems.gfg;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;


class feststQueueSolution {
    public static long sumOfPowersOptimized(long a, long b) {
        // code here
        int ans = 0;
        for(long i=a;i<=b;i++){
            ans+=primes(i);
        }
        return ans;
    }
    public static long primes(long n){
        int ans = 0;

        for(int i=2;i*i<=n;i++){
            while(n%i==0){
                ans++;
                n/=i;
            }
        }
        if(n!=1){
            ans++;
        }
        return ans;
    }
    public static long sumOfPowers(long a, long b) {
        // code here
        Map<Long, Integer> countMap = new HashMap<>();
        for(long num= a; num<= b;num++){
            long inputNumber = num;
            for(int div = 2; div * div <= inputNumber; div++){
                while(inputNumber % div ==0){
                    inputNumber = inputNumber / div;
                    int value = countMap.getOrDefault(inputNumber,0);
                    countMap.put(inputNumber, value+1);
                }
            }
            if(inputNumber != 1){
                int value = countMap.getOrDefault(inputNumber,0);
                countMap.put(inputNumber, value+1);
            }

        }
        return countMap.entrySet().stream().mapToInt(f->  f.getValue()).sum();
    }
}
public class TechfestQueue {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(reader.readLine());
        while (t-- > 0) {
            long a = Long.parseLong(reader.readLine().trim());
            long b = Long.parseLong(reader.readLine().trim());
            feststQueueSolution solution = new feststQueueSolution();
            long ans = solution.sumOfPowers(a, b);
            System.out.println(ans);
        }

    }
}


Comments

Post a Comment

Popular posts from this blog

Primitive Data Types in java

By -
Image
Primitive Data Types   Expect boolean and char remaining data types are consider assigned data types because we can represent both positive and negative numbers. byte : size : 1 byte  ( 8 bit) max value : 127 min value: 128 Range: -128 to 127 a byte is the best choice,  if we want to handle data in terms of streams either from file or form the network. syntax : byte b = 10; Default value : 0 short: size: 2 bytes (16 bit) Range: - 2 power 15 to 2 power 15 -1 the short data type is best suitable for 16-bit processors like 8085 but these processors are completed outdated and hence corresponding data type is also outdated datatype. syntax : short b = 10; Default value : 0 int : size: 4 bytes (32 bit) Range: -2 power 31 to 2 power 31 -1 syntax :  int b = 10; Default value : 0 long : size: 8 bytes (64 bit) Range : - 2 power 63 to 2 power 63 -1  syntax : long b = 1051541; Default value : 0 All the above data types (byte, short, int, long ) use to represent integral val...
Read more

let - Keyword in JavaScript (Block scope)

By -
Image
Before ES2015  javascript variable has only two scopes i.e.  Global Scope   and   Function Scope . but in ES2015 they introduced the let keyword. this keyword provides Block scope variables. Block scope means  Variables declared inside a block  {}  cannot be accessed from outside the block. For Example : function getPersonDetails(){       var name ="Nilesh";       let newName = "Nil" } console.log("Print variable with var "+ name);    // you can access name variable outside function console.log("print variable value with let"+newName);  // you can not access newName Variable outside. In the above example getPersonDetails is a function that contains two variables "name " and "newName" with the keyword var and let. hear you can access the name variable which is declared with var keyword outside of the function. but you can not access the newName variables which is declared with the let keyword outside of the f...
Read more

Coding Problem 4: Smallest window containing 0, 1 and 2 [GFG - Problem Solving]

By -
  Given a string   S   consisting of the characters   0 ,   1   and   2 . Your task is to find the length of the   smallest substring  of string   S   that contains all the three characters   0, 1  and   2 . If no such substring exists, then return   -1 . Example 1: Input: S = 10212 Output: 3 Explanation: The substring 102 is the smallest substring that contains the characters 0, 1 and 2. Example 2: Input: S = 12121 Output: -1 Explanation: As the character 0 is not present in the string S, therefor no substring containing all the three characters 0, 1 and 2 exists. Hence, the answer is -1 in this case. Your Task: Complete the function  smallestSubstring()  which takes the string  S  as input, and returns the length of the  smallest substring  of string S that contains all the three characters  0, 1  and  2. Expected Time Complexity:  O( length( S ) ) Expecte...
Read more