Chef and Interview Codechef Solution

Hello Programmers In this post, you will know how to solve the Chef and Interview Codechef Solution.

Chef and Interview Codechef Solution
Chef and Interview Codechef Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

Chef wants to hire a new assistant. He published an advertisement regarding that in a newspaper. After seeing the advertisement, many candidates have applied for the job. Now chef wants to shortlist people for the interviews, so he gave all of them one problem which they must solve in order to get shortlisted.

The problem was : For a given positive integer N, what is the maximum sum of distinct numbers such that the Least Common Multiple of all these numbers is N.

Your friend Rupsa also applied for the job, but was unable to solve this problem and hence you’ve decided to help her out by writing a code for solving this problem.

Input

The first line of the input contains an integer T denoting the number of test cases.

Each test case contains a single integer N.

Output

For each test case, output a single line containing an integer corresponding to the answer for that test case.

Constraints

  • 1 ≤ T ≤ 1000
  • 1 ≤ N ≤ 109

Subtask 1 (30 points):

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 105

Subtask 2 (70 points):

  • original constraints

Sample Input 1 

2
1
2

Sample Output 1 

1
3

Explanation

Example 1 : Only possible number is 1, so the maximum sum of distinct numbers is exactly 1.
Example 2 : The distinct numbers you can have are just 1 and 2, so the sum is 3. If we consider any other number greater than 2, then the least common multiple will be more than 2.

Chef and Interview CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	   static class FastReader {
            BufferedReader br;
            StringTokenizer st;
            public FastReader() {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }
            int nextInt() {
                return Integer.parseInt(next());
            }
            long nextLong() {
                return Long.parseLong(next());
            }
            double nextDouble() {
                return Double.parseDouble(next());
            }
            float nextFloat() {
                return Float.parseFloat(next());
            }
            String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (Exception e) {
                    e.printStackTrace();
                }
                return str;
            }
            char nextChar() {
                char c = ' ';
                try {
                    c = (char) br.read();
                } catch (Exception e) {
                    e.printStackTrace();
                }
                return c;
            }
    }
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int ntc = sc.nextInt();
        while(ntc -- > 0)
        {
            int N = sc.nextInt();
            long sum = 0;
            for (int i = 1; i * i <=N ;i++) {
                if(N % i == 0)
                {
                    sum +=i;
                    if(i != N/i)
                    {
                        sum +=N/i;
                    }
                }
            }
            System.out.println(sum);
        }
    }
}

Chef and Interview CodeChef Solutions in CPP

#include <iostream>
using namespace std;
int main() {
	 int t;
    cin>>t;
    for(int i = 1; i <= t; i++){
        int n, p;
        long long sum = 0;
        cin >> n;
        for(p = 1; p * p <= n; p++){
            if(n % p == 0){
                sum += p;
                if(p != n / p){
                    sum += n / p;
                }
            }
        }
        cout << sum << '\n';
    }
    return 0;
}

Chef and Interview CodeChef Solutions in Python

import math
for _ in range(int(input())):
    n=int(input())
    p=int(math.sqrt(n))
    ans=0
    for i in range(1,p+1):
        if n%i==0:
            q=int(n/i)
            if q==i:
                ans+=i
            else:
                ans+=i+q
    print(ans)

Disclaimer: The above Problem (Chef and Interview) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Chef On Island Codechef Solution

Leave a Reply

Your email address will not be published. Required fields are marked *