Test Time on Segmented & Incremental Sieve PDF

 TEST TIME ON SEGMENTED AND INCREMENTAL SIEVE URL:https://forms.gle/geq3XgXnt7WCk3qMA QR CODE: EULER’S PHI ALGORITHM TOPICS Introduction Examples Properties Coding Interview Questions INTRODUCTION Euler's totient function...

 TEST TIME ON SEGMENTED AND INCREMENTAL SIEVE URL:https://forms.gle/geq3XgXnt7WCk3qMA QR CODE: EULER’S PHI ALGORITHM TOPICS Introduction Examples Properties Coding Interview Questions INTRODUCTION Euler's totient function (also called phi-function or totient function) takes a single positive integer n as input and outputs the number of integers present between 1 and n that are co-prime to n. Note: 2 positive integers a and b are said to be co-prime if their greatest common factor/divisor is equal to 1, that is, gcd(a,b)=1 1 is considered co-prime to all numbers. Example:1 Find (5) Solution Here n=5 Numbers Euler’s less than Phi Algorithm 5 are 1,2,3 and 4 GCD Relatively Prime? GCD(1,5)=1 GCD(2,5)=1 GCD(3,5)=1 GCD(4,5)=1 there are 4 numbers less than 5 that are co-prime to it Therefore (5)=4 Example:2 Find (11) Solution Here n=11 Numbers less than 11 Phi Euler’s are Algorithm 1,2,3,4,5,6,7,8,9 and 10 GCD Relatively GCD Relatively Prime? Prime? GCD(1,11)=1 GCD(6,11)=1 GCD(2,11)=1 GCD(7,11)=1 GCD(3,11)=1 GCD(8,11)=1 GCD(4,11)=1 GCD(9,11)=1 GCD(5,11)=1 GCD(10,11)= 1 there are 10 numbers less than 11 that are co-prime to it Therefore (11)=10 Example:3 Find (8) Solution Here n=8 Numbers less than 8 are 1,2,3,4,5,6 and 7 Euler’s Phi Algorithm GCD Relatively GCD Relatively Prime? Prime? GCD(1,8)=1 GCD(5,8)=1 GCD(2,8)=2 GCD(6,8)=2 GCD(3,8)=1 GCD(7,8)=1 GCD(4,8)=4 there are 4 numbers less than 8 that are co-prime to it Therefore (8)=4 Properties Criteria of 'n' Formula 'n' is prime. Φ(n) = (n-1) Φ(n) n = p x q Φ(n) = (p-1) × (q-1) 'p' and 'q' are primes. n = a x b. Either 'a' or 'b’ is composite. Both 'a' and 'b' are composite. Property 1 Φ(n) Criteria of 'n' Formula 'n' is prime. Φ(n) = (n-1) Proof Find Φ(7) Here n=7 ‘n’ is a prime number Φ(n) = (n-1) Φ(7) = (7-1) Φ(7) = 6 there are 6 numbers less than 7 that are co-prime to it Therefore (7)=6 Property 2 Criteria of 'n' Formula Φ(n) n = p x q Φ(n) = (p-1) × (q-1) 'p' and 'q' are primes. Proof Find Φ(35) Here n=35 ‘n’ is a product of two prime numbers 5 and 7 Let us assign p=5 and q=7. Φ(n)=(p-1) × (q-1) Φ(35)=(5-1) × (7-1) = 4 x 6 = 24 So, there are 24 numbers that are lesser than 35 and relatively prime to 35. Property 3 Criteria of 'n' Formula Φ(n) n = a x b. Either 'a' or 'b’ is composite. Both 'a' and 'b' are composite. Basic Algorithm A simple solution is to iterate through all numbers from 1 to n-1 and count numbers with gcd java.io.*; import with n if (gcd(i, n) == 1) class Main { result++; // Function to return GCD of a return result; and b } static int gcd(int a, int b) public static void main(String[] { args) if (a == 0) { return b; int n=5; return gcd(b % a, a); //Finding Phi for input n } static int phi(int n) { System.out.println(phi(n)); int result = 1; } for (int i = 2; i < n; i++) } Time Complexity: O(N log N) Better Solution Algorithm 1) Initialize: result = n 2) Run a loop from 'p' = 2 to sqrt(n), do following for every 'p'. a) If p divides n, then Set: result = result * (1.0 - (1.0 / (float) p)); Divide all occurrences of p in n. 3) Return the result import java.io.*; class Main { static int phi(int n) { float result = n; for (int p = 2; p * p 1) result -= result / n; return (int) result; } public static void main(String args[]) { int n = 35; System.out.println("phi(" + n + ") = " + phi(n)); } } Better Solution - 2 We can avoid floating-point calculations in the above method. The idea is to count all prime factors and their multiples and subtract this count from n to get the totient function value (Prime factors and multiples of prime factors won’t have GCD as 1) Algorithm 1) Initialize result as n 2) Consider every number 'p' (where 'p' varies from 2 to Φn). If p divides n, then do following a) Subtract all multiples of p from 1 to n [all multiples of p will have gcd more than 1 (at least p) with n] b) Update n by repeatedly dividing it by p. 3) If the reduced n is more than 1, then remove all multiples of n from result. Program import java.io.*; class Main { static int phi(int n) { int result = n; for (int p = 2; p * p 1) result -= result / n; return result; } public static void main (String[] args) { int n=1000; System.out.println(phi(n)); } } INTERVIEW QUESTIONS Interview questions What is Euler's Phi algorithm? Answer: Euler's Phi algorithm is a mathematical algorithm used to calculate the totient function of a given number. The totient function (φ(n)) is the number of positive integers less than or equal to n that are relatively prime to n. Interview questions What is the time complexity of Euler's Phi algorithm? Answer: The time complexity of Euler's Phi algorithm is O(sqrt(n)), where n is the input number. Interview questions What are some applications of Euler's Phi algorithm? Answer: Euler's Phi algorithm has several applications in number theory and cryptography. It is used in RSA encryption and decryption, as well as in the generation of keys for public key cryptography. It is also used in determining the order of an element in a group, and in solving the discrete logarithm problem. Interview questions Can Euler's Phi algorithm be used for large numbers? Answer: Euler's Phi algorithm can be used for large numbers, but it may become computationally expensive due to the prime factorization step. In some cases, it may be necessary to use more advanced algorithms for calculating the totient function of very large numbers. Interview questions What is the significance of Euler's Phi function? Answer: Euler's Phi function is significant in number theory and cryptography as it is used in many mathematical proofs and algorithms. It has applications in determining the relative primality of two numbers, generating RSA keys, and solving the discrete logarithm problem, among other things. Interview questions How does Euler's Phi algorithm differ from the Sieve of Eratosthenes? Answer: Euler's Phi algorithm and the Sieve of Eratosthenes are two different algorithms used in number theory. The Sieve of Eratosthenes is used to find all the prime numbers up to a given limit, while Euler's Phi algorithm is used to calculate the totient function of a given number. The two algorithms have different purposes and use different methods to accomplish their respective tasks. Practice questions Question 1: Understanding Euler's Totient Function Explain the concept of Euler's Totient Function (φ) and its significance in number theory. How does the provided Java code calculate Euler's Totient Function for a given integer `n`? Provide a step-by-step explanation of the algorithm used in the code. Practice questions Question 2: Analyzing Time Complexity Analyze the time complexity of the `phi` method in the provided Java code. Consider the worst-case scenario and discuss how the time complexity is determined based on the input value `n`. Suggest any possible optimizations to improve the time complexity of the algorithm. Practice questions Question 3: Handling Large Inputs Discuss the limitations of the provided code when dealing with large input values of `n`. Identify potential issues that may arise due to the data type used for the `result` variable in the `phi` method. Propose alternative approaches to handle large inputs efficiently while ensuring accuracy in calculating Euler's Totient Function. Practice questions Question 4: Write a Java program to calculate Euler's Totient Function (φ) for a given integer input n. Euler's Totient Function φ(n) for an input n is defined as the count of positive integers less than or equal to n that are coprime to n.  THANK YOU +91 78150 95095 [email protected] www.codemithra.com  TEST TIME ON EULER’S PHI ALGORITHM URL: https://forms.gle/hghiSo2Yd4KmiExg6 QR CODE: STROBOGRAMMATIC NUMBER TOPICS Introduction Explanation Coding Complexity Analysis Interview Questions INTRODUCTION A strobogrammatic number is a number that looks the same when rotated 180 degrees (upside down). In other words, a strobogrammatic number is a number that appears the same when viewed upside down on a seven-segment display, like the numbers 0, 1, 8, 6, and 9. Here are the strobogrammatic numbers: 0: looks the same upside down 1: looks the same upside down 8: looks the same upside down 6: looks like 9 upside down 9: looks like 6 upside down INTRODUCTION Strobogrammatic numbers are interesting in math and computer science because they have some unique properties. For example, they are often used in programming for things like checking whether a number is a palindrome (a number that reads the same forwards and backward). Strobogrammatic numbers can also be used to create strobogrammatic palindromes, which are words or phrases that read the same when rotated 180 degrees. Examples of strobogrammatic palindromes include "NOON", "EYE", and "SOS". EXPLANATION The first few strobogrammatic numbers are: 0, 1, 8, 11, 69, 88, 96, 101, 111, 181, 609, 619, 689, 808, 818, 888, 906, 916, 986, 1001, 1111, 1691, 1881, 1961, 6009, 6119, 6699, 6889, 6969, 8008, 8118, 8698, 8888, 8968, 9006, 9116, 9696, 9886, 9966,... Program 1 list of all the Strobogrammatic numbers that have a length of 3 import java.util.*; public class EthCode{ public static ArrayList StrobogrammaticNum(int n){ ArrayList result = numDef(n,n); return result;} public static ArrayList numDef(int n, int length){ if(n==0) return new ArrayList(Arrays.asList(new String[] {""})); if(n==1) return new ArrayList(Arrays.asList(new String[] {"1", "0", "8"})); ArrayList middles = numDef(n - 2, length); ArrayList result = new ArrayList(); Program 1 list of all the Strobogrammatic numbers that have a length of 3 for(String middle: middles){ if(n != length) result.add("0" + middle + "0"); result.add("8" + middle + "8"); result.add("1" + middle + "1"); result.add("9" + middle + "6"); result.add("6" + middle + "9"); }return result; } public static void main(String args[]){ System.out.println(StrobogrammaticNum(3)); }} Program 2 Given number n, check if it is a Strobogrammatic Number. Sample IO Input: "69" Output: 69 is a strobogrammatic number Input: "88" Output: 88 is a strobogrammatic number Input: "962" Output: 962 is not a strobogrammatic number import java.util.*; public class StrobogrammaticNumber { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter a number: "); String num = sc.nextLine(); if(isStrobogrammatic(num)) { System.out.println(num + " is a strobogrammatic number"); } else { System.out.println(num + " is not a strobogrammatic number"); } sc.close(); } public static boolean isStrobogrammatic(String num) { Map strobogrammaticDictonary = new HashMap(); strobogrammaticDictonary.put('0', '0'); strobogrammaticDictonary.put('1', '1'); strobogrammaticDictonary.put('6', '9'); strobogrammaticDictonary.put('8', '8'); strobogrammaticDictonary.put('9', '6'); int n = num.length(); for(int i = 0 , j = (n-1) ; i (right shift) 7. >>> (unsigned right shift) Operators 1. "&" (bitwise AND): Performs a bitwise AND operation between the binary representations of two integers. Each bit of the result is set to 1 only if the corresponding bits of both operands are 1. Example: int num1 = 12; // Binary: 1100 int num2 = 10; // Binary: 1010 int result = num1 & num2; // Binary result: 1000 (8 in decimal) Operators 2. "|" (bitwise OR): Performs a bitwise OR operation between the binary representations of two integers. Each bit of the result is set to 1 if at least one of the corresponding bits in either operand is 1. Example: int num3 = 12; // Binary: 1100 int num4 = 10; // Binary: 1010 int result = num3 | num4; // Binary result: 1110 (14 in decimal) Operators 2. "|" (bitwise OR): Performs a bitwise OR operation between the binary representations of two integers. Each bit of the result is set to 1 if at least one of the corresponding bits in either operand is 1. Example: int num3 = 12; // Binary: 1100 int num4 = 10; // Binary: 1010 int result = num3 | num4; // Binary result: 1110 (14 in decimal) Operators 3. "^" (bitwise XOR): Performs a bitwise XOR (exclusive OR) operation between the binary representations of two integers. Each bit of the result is set to 1 if the corresponding bits of the operands are different (one 0 and one 1). Example: int num5 = 12; // Binary: 1100 int num6 = 10; // Binary: 1010 int result = num5 ^ num6; // Binary result: 0110 (6 in decimal) Operators 4. "~" (bitwise NOT): Performs a bitwise NOT operation, which flips the bits of an integer. Each 0 bit in the original number becomes 1, and each 1 bit becomes 0. Example: int num7 = 12; // Binary: 1100 int result = ~num7; // Binary result: 0011 (3 in decimal) Operators 5. "" (right shift): Shifts the bits of an integer to the right by the specified number of positions. The leftmost bit is filled with the sign bit (in case of a signed data type) or with zeros (in case of an unsigned data type). Example: int num9 = -8; // Binary: 11111000 int result = num9 >> 2; // Binary result: 11111110 (-2 in decimal) Operators 7. ">>>" (unsigned right shift): Similar to ">>", but the leftmost bits are always filled with zeros, regardless of the sign of the number. Example: int num10 = -8; // Binary: 11111000 int result = num10 >>> 2; // Binary result: 00111110 (62 in decimal) Operators Conditional (Ternary) Operator: The conditional operator, also known as the ternary operator, is a compact way to express a simple if-else statement in Java. It has the following syntax: condition ? expression1 : expression2 The condition is evaluated first, and if it is true, then expression1 is returned; otherwise, expression2 is returned. The conditional operator is useful for assigning a value based on a condition in a concise manner. Operators Example: int x = 10; int y = 5; int result = (x > y) ? x : y; // The above line is equivalent to the following if-else statement: // int result; // if (x > y) { // result = x; // } else { // result = y; // } In this example, the result variable will be assigned the value of x (which is 10) because the condition `x > y` is true. Operators Example: int x = 10; int y = 5; int result = (x > y) ? x : y; // The above line is equivalent to the following if-else statement: // int result; // if (x > y) { // result = x; // } else { // result = y; // } In this example, the result variable will be assigned the value of x (which is 10) because the condition `x > y` is true. Interview questions 1. How do you receive input in Java? In Java, you can use the `Scanner` class to receive input from the user. First, you need to import it using `import java.util.Scanner;`, then create a `Scanner` object to read input. Interview questions 2. What's the step-by-step process of receiving input in Java? 1. Import the `Scanner` class. 2. Create a `Scanner` object by calling `Scanner scanner = new Scanner(System.in);`. 3. Prompt the user for input using `System.out.print` or `System.out.println`. 4. Read input using `scanner.next()`, `scanner.nextInt()`, etc. Interview questions 3. How can you print output in Java? You can use the `System.out.print` or `System.out.println` statements to display output in the console. Interview questions 4. What's the difference between `System.out.print` and `System.out.println`? `System.out.print` prints text without moving to the next line, while `System.out.println` adds a line break after printing the text.  Interview questions 5. What are operators in Java? Operators are symbols that perform operations on variables and values.  Practice Questions Question 1: Basic Input and Output Write a Java program to read a user's name and age, then print a greeting message that includes their name and age. Sample Input: Enter your name: Alice Enter your age: 30 Expected Output: Hello, Alice! You are 30 years old.  Practice Questions Question 2: Sum of Two Numbers Write a Java program to read two integers from the user and print their sum. Sample Input: Enter first number: 15 Enter second number: 25 Expected Output: The sum is: 40  Practice Questions Question 3: Temperature Conversion Write a Java program that reads a temperature in Celsius from the user and converts it to Fahrenheit. The formula is: `F = (C * 9/5) + 32`. Sample Input: Enter temperature in Celsius: 100 Expected Output: Temperature in Fahrenheit: 212.0  Practice Questions Question 4: Area of a Circle Write a Java program to read the radius of a circle from the user and calculate its area. The formula is: `Area = π * r^2`. Sample Input: Enter the radius of the circle: 7 Expected Output: The area of the circle is: 153.93804002589985  Practice Questions Question 5: Basic Arithmetic Operations Write a Java program that reads two integers from the user and performs addition, subtraction, multiplication, and division, then prints the results. Sample Input: Enter first number: 20 Enter second number: 4 Expected Output: Sum: 24 Difference: 16 Product: 80 Division: 5.0  THANK YOU +91 78150 95095 [email protected] www.codemithra.com  Test time on basic input,output,operators URL:https://forms.gle/vLep53Dn1cNGn6ks9 QR CODE: DECISION MAKING AND CONTROL STATEMENT TOPICS What is decision making? If If-else If-else If-else statement Switch Ternary operator Jump statements What is decision-making? Decision-making statements are used to control the flow of a program based on certain conditions. These statements allow you to make decisions and execute different blocks of code depending on whether a given condition is true or false. 1. if statement: The "if" statement is the fundamental decision-making statement. It evaluates a boolean expression inside the parentheses and executes the block of code within the curly braces if the condition if (condition) { is true. // Code to be executed if the condition is true } Example public class Main { public static void main(String[] args) { int number = 10; if (number > 5) { System.out.println("The number is greater than 5."); } } } 2.if-else statement: The "if-else" statement provides an alternative block of code to be executed when the condition is false. if (condition) { // Code to be executed if the condition is true } else { // Code to be executed if the condition is false } public class Main { public static void main(String[] args) { int number = 3; if (number % 2 == 0) { System.out.println("The number is even."); } else { System.out.println("The number is odd."); } } } 3. if-else if-else statement: The "if-else if-else" statement allows you to chain multiple conditions together and execute different blocks of code based on the first condition that evaluates to true. if (condition1) { // Code to be executed if condition1 is true } else if (condition2) { // Code to be executed if condition 2 is true } else { // Code to be executed if all previous conditions are false } public class Main { public static void main(String[] args) { int score = 85; if (score >= 90) { System.out.println("A"); } else if (score >= 80) { System.out.println("B"); } else if (score >= 70) { System.out.println("C"); } else { System.out.println("D"); }}} 4. switch statement: The "switch" statement provides an alternative way to handle multiple conditions based on the value of an expression. It allows you to choose a specific block of code to execute based on different possible values. switch (expression) { case value1: // Code to be executed if the expression equals value1 break; case value2: // Code to be executed if the expression equals value2 break; // More cases can be added here default: // Code to be executed if none of the cases match the expression } decision making statements Ternary operator (?:): It is a shorthand way to write simple if-else statements. int num = 10; String result = (num > 0) ? "Positive" : "Non-positive"; System.out.println(result); decision making statements-Jump statements There are three jump statements: Break Continue Return These statements are used to control the flow of a program and are typically used in loops and conditional blocks. decision making statements-Jump statements 1. break: The `break` statement is used to exit a loop prematurely, even if the loop condition is not met. When the `break` statement is encountered, the control flow exits the loop, and the program continues with the statement after the loop. Example public class Main { public static void main(String[] args) { for (int i = 1; i