Check if N leaves only distinct remainders on division by all values up to K
Given a two integers N and K, the task is to check if N leaves only distinct remainders when divided by all integers in the range [1, K]. If so, print Yes. Otherwise, print No.
Examples:
Input: N = 5, K = 3
Output: Yes
Explanation:
(5 % 1) == 0
(5 % 2) == 1
(5 % 3) == 2
Since all the remainders {0, 1, 2} are distinct.
Input: N = 5, K = 4
Output: No
Explanation:
(5 % 1) == 0
(5 % 2) == 1
(5 % 3) == 2
(5 % 4) == 1, which is not distinct.
Approach:
Follow the steps given below to solve the problem:
- Initialize a set S
- Iterate over the range [1, K].
- In each iteration, check if N % i is already present in the Set S or not.
- If not present, then insert N % i into the set S
- Otherwise, print No and terminate.
Below is the implementation of the above approach:
C++
// C++ Program to check if all // remainders are distinct or not #include <bits/stdc++.h> using namespace std; // Function to check and return // if all remainders are distinct bool is_distinct( long long n, long long k) { // Stores the remainder unordered_set< long long > s; for ( int i = 1; i <= k; i++) { // Calculate the remainder long long tmp = n % i; // If remainder already occurred if (s.find(tmp) != s.end()) { return false ; } // Insert into the set s.insert(tmp); } return true ; } // Driver Code int main() { long long N = 5, K = 3; if (is_distinct(N, K)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program to check if all // remainders are distinct or not import java.util.*; class GFG{ // Function to check and return // if all remainders are distinct static boolean is_distinct( long n, long k) { // Stores the remainder HashSet<Long> s = new HashSet<Long>(); for ( int i = 1 ; i <= k; i++) { // Calculate the remainder long tmp = n % i; // If remainder already occurred if (s.contains(tmp)) { return false ; } // Insert into the set s.add(tmp); } return true ; } // Driver Code public static void main(String[] args) { long N = 5 , K = 3 ; if (is_distinct(N, K)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program to check if all # remainders are distinct or not # Function to check and return # if all remainders are distinct def is_distinct(n, k): # Stores the remainder s = set () for i in range ( 1 , k + 1 ): # Calculate the remainder tmp = n % i # If remainder already occurred if (tmp in s): return False # Insert into the set s.add(tmp) return True # Driver Code if __name__ = = '__main__' : N = 5 K = 3 if (is_distinct(N, K)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Shivam Singh |
C#
// C# program to check if all // remainders are distinct or not using System; using System.Collections.Generic; class GFG{ // Function to check and return // if all remainders are distinct static bool is_distinct( long n, long k) { // Stores the remainder HashSet< long > s = new HashSet< long >(); for ( int i = 1; i <= k; i++) { // Calculate the remainder long tmp = n % i; // If remainder already occurred if (s.Contains(tmp)) { return false ; } // Insert into the set s.Add(tmp); } return true ; } // Driver Code public static void Main(String[] args) { long N = 5, K = 3; if (is_distinct(N, K)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program to check if all // remainders are distinct or not // Function to check and return // if all remainders are distinct function is_distinct(n, k) { // Stores the remainder let s = new Set(); for (let i = 1; i <= k; i++) { // Calculate the remainder let tmp = n % i; // If remainder already occurred if (s.has(tmp)) { return false ; } // Insert into the set s.add(tmp); } return true ; } // Driver code let N = 5, K = 3; if (is_distinct(N, K)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by souravghosh0416. </script> |
Output:
Yes
Time complexity: O(K)
Auxiliary space: O(K)