Given an integer x, the task is to find if every k-cycle shift on the element produces a number greater than or equal to the same element.
A k-cyclic shift of an integer x is a function that removes the last k digits of x and inserts them in its beginning.
For example, the k-cyclic shifts of 123 are 312 for k=1 and 231 for k=2. Print Yes if the given condition is satisfied else print No.
Examples:
Input: x = 123
Output : Yes
The k-cyclic shifts of 123 are 312 for k=1 and 231 for k=2.
Both 312 and 231 are greater than 123.
Input: 2214
Output: No
The k-cyclic shift of 2214 when k=2 is 1422 which is smaller than 2214
Simple Approach:
Approach:
- Read the input number x.
- Compute the number of digits in x using log10(x) + 1, and store the result in n.
- For each value of k from 1 to n-1, do the following:
- Compute the k-cyclic shift of x using (x % (int)pow(10, k)) * (int)pow(10, n-k) + x / (int)pow(10, k), and store the result in k_shift.
- If k_shift is smaller than x, return false.
- If all k-cyclic shifts are greater than or equal to x, return true.
- Output “Yes” if the function returns true, and “No” otherwise.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;bool check_all_k_shifts(int x) { int n = log10(x) + 1; // compute number of digits in x for (int k = 1; k < n; k++) { int k_shift = (x % (int)pow(10, k)) * (int)pow(10, n-k) + x / (int)pow(10, k); // compute k-cyclic shift of x if (k_shift < x) { // check if k-cyclic shift is smaller than x return false; // if so, return false } } return true; // if all k-cyclic shifts are greater than or equal to x, return true}int main() { int x=2214; if (check_all_k_shifts(x)) { cout << "Yes\n"; } else { cout << "No\n"; } return 0;} |
Java
import java.util.*;public class Main { public static boolean checkAllKShifts(int x) { int n = (int) (Math.log10(x) + 1); // compute number of digits in x for (int k = 1; k < n; k++) { int kShift = (x % (int) Math.pow(10, k)) * (int) Math.pow(10, n - k) + x / (int) Math.pow(10, k); // compute k-cyclic shift of x if (kShift < x) { // check if k-cyclic shift is smaller than x return false; // if so, return false } } return true; // if all k-cyclic shifts are greater than or equal to x, return true } public static void main(String[] args) { int x = 2214; if (checkAllKShifts(x)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python
import mathdef check_all_k_shifts(x): n = int(math.log10(x)) + 1 # compute number of digits in x for k in range(1, n): k_shift = (x % 10**k) * 10**(n-k) + \ x // 10**k # compute k-cyclic shift of x if k_shift < x: # check if k-cyclic shift is smaller than x return False # if so, return false return True # if all k-cyclic shifts are greater than or equal to x, return truedef main(): x = 2214 if check_all_k_shifts(x): print("Yes") else: print("No")if __name__ == "__main__": main() |
C#
using System;class GFG{ static bool CheckAllKShifts(int x) { int n = (int)Math.Log10(x) + 1; // compute number of digits in x for (int k = 1; k < n; k++) { int kShift = (x % (int)Math.Pow(10, k)) * (int)Math.Pow(10, n - k) + x / (int)Math.Pow(10, k); // compute k-cyclic shift of x if (kShift < x) // check if k-cyclic shift is smaller than x { return false; // if so, return false } } return true; // if all k-cyclic shifts are greater than or equal to x, return true } static void Main(string[] args) { int x = 2214; if (CheckAllKShifts(x)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
function checkAllKShifts(x) { let n = Math.floor(Math.log10(x)) + 1; // compute number of digits in x for (let k = 1; k < n; k++) { let kShift = (x % Math.pow(10, k)) * Math.pow(10, n - k) + Math.floor(x / Math.pow(10, k)); // compute k-cyclic shift of x if (kShift < x) { // check if k-cyclic shift is smaller than x return false; // if so, return false } } return true; // if all k-cyclic shifts are greater than or equal to x, return true}// Test the checkAllKShifts functionlet x = 2214;if (checkAllKShifts(x)) { console.log("Yes");} else { console.log("No");} |
Output
No
Time Complexity: O(n^2), where n represents the length of the given string.
Space complexity: O(1).
Approach: Simply find all the possible k cyclic shifts of the number and check if all are greater than the given number or not.
Below is the implementation of the above approach:
C++
// CPP implementation of the approach#include<bits/stdc++.h>using namespace std;void CheckKCycles(int n, string s) { bool ff = true; int x = 0; for (int i = 1; i < n; i++) { // Splitting the number at index i // and adding to the front x = (s.substr(i) + s.substr(0, i)).length(); // Checking if the value is greater than // or equal to the given value if (x >= s.length()) { continue; } ff = false; break; } if (ff) { cout << ("Yes"); } else { cout << ("No"); }}// Driver codeint main() { int n = 3; string s = "123"; CheckKCycles(n, s); return 0;}/* This code contributed by Rajput-Ji */ |
Java
// Java implementation of the approachclass GFG { static void CheckKCycles(int n, String s) { boolean ff = true; int x = 0; for (int i = 1; i < n; i++) { // Splitting the number at index i // and adding to the front x = (s.substring(i) + s.substring(0, i)).length(); // Checking if the value is greater than // or equal to the given value if (x >= s.length()) { continue; } ff = false; break; } if (ff) { System.out.println("Yes"); } else { System.out.println("No"); } } // Driver code public static void main(String[] args) { int n = 3; String s = "123"; CheckKCycles(n, s); }}/* This code contributed by PrinciRaj1992 */ |
Python
# Python3 implementation of the approachdef CheckKCycles(n, s): ff = True for i in range(1, n): # Splitting the number at index i # and adding to the front x = int(s[i:] + s[0:i]) # Checking if the value is greater than # or equal to the given value if (x >= int(s)): continue ff = False break if (ff): print("Yes") else: print("No")n = 3s = "123"CheckKCycles(n, s) |
C#
// C# implementation of the approachusing System;class GFG { static void CheckKCycles(int n, String s) { bool ff = true; int x = 0; for (int i = 1; i < n; i++) { // Splitting the number at index i // and adding to the front x = (s.Substring(i) + s.Substring(0, i)).Length; // Checking if the value is greater than // or equal to the given value if (x >= s.Length) { continue; } ff = false; break; } if (ff) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } // Driver code public static void Main(String[] args) { int n = 3; String s = "123"; CheckKCycles(n, s); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// javascript implementation of the approachfunction CheckKCycles(n, s) { var ff = true; var x = 0; for (i = 1; i < n; i++) { // Splitting the number at index i // and adding to the front x = (s.substring(i) + s.substring(0, i)).length; // Checking if the value is greater than // or equal to the given value if (x >= s.length) { continue; } ff = false; break; } if (ff) { document.write("Yes"); } else { document.write("No"); }}// Driver code var n = 3; var s = "123"; CheckKCycles(n, s);// This code is contributed by 29AjayKumar </script> |
PHP
<?php// PHP implementation of the approachfunction CheckKCycles($n, $s) { $ff = true; $x = 0; for ($i = 1; $i < $n; $i++) { // Splitting the number at index i // and adding to the front $x = strlen(substr($s, $i).substr($s, 0, $i)); // Checking if the value is greater than // or equal to the given value if ($x >= strlen($s)) { continue; } $ff = false; break; } if ($ff) { print("Yes"); } else { print("No"); }}// Driver code$n = 3;$s = "123";CheckKCycles($n, $s);// This code contributed by mits ?> |
Output
Yes
Time Complexity: O(N2), where N represents the length of the given string.
The time complexity of the program is O(N2) because first it runs a loop for traversing the string and inside that substring function is used.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Approach 2:
Here’s another approach to solve the same problem:
- Iterate through all possible k values from 1 to n/2.
- For each k value, check if the string can be split into k cycles of length n/k. To do this, compare the substring of the original string from 0 to n/k with the substring of the original string from i*(n/k) to (i+1)*(n/k), for all i from 1 to k-1.
- If the string can be split into k cycles of length n/k, then it satisfies the given condition. Return “Yes”.
- If the string cannot be split into any cycles, then return “No”.
Here’s the code of this approach:
C++
#include <iostream>#include <string>using namespace std;string hasKCycles(int n, string s) { for (int k = 1; k <= n/2; k++) { if (n % k != 0) { continue; } int len = n/k; bool flag = true; for (int i = 1; i < k; i++) { if (s.substr((i-1)*len, len) != s.substr(i*len, len)) { flag = false; break; } } if (flag) { return "Yes"; } } return "No";}int main() { int n = 3; string s = "123"; cout << hasKCycles(n, s) << endl; return 0;} |
Java
import java.util.*;public class Main { public static void main(String[] args) { int n = 3; String s = "123"; System.out.println(hasKCycles(n, s)); } public static String hasKCycles(int n, String s) { for (int k = 1; k <= n/2; k++) { if (n % k != 0) { continue; } int len = n/k; boolean flag = true; for (int i = 1; i < k; i++) { if (!s.substring((i-1)*len, i*len).equals(s.substring(i*len, (i+1)*len))) { flag = false; break; } } if (flag) { return "Yes"; } } return "No"; }} |
Python3
def has_k_cycles(n, s): # Iterate from 1 to n/2 to find potential cycle lengths (k) for k in range(1, n // 2 + 1): # If n is not divisible by k, it cannot have k cycles if n % k != 0: continue len_ = n // k # Calculate the length of each substring flag = True # Initialize a flag to check if all substrings are the same # Iterate through the substrings and check if they are the same for i in range(1, k): # Compare substrings at (i-1)*len to i*len if s[(i - 1) * len_ : i * len_] != s[i * len_ : (i + 1) * len_]: flag = False break # If all substrings are the same, return "Yes" if flag: return "Yes" # If no k cycles are found, return "No" return "No"if __name__ == "__main__": n = 3 s = "123" result = has_k_cycles(n, s) print(result) |
C#
using System;class Program{ // Function to check if a string has k cycles of equal length static string HasKCycles(int n, string s) { // Iterate through all possible values of k from 1 to n/2 for (int k = 1; k <= n / 2; k++) { // Check if n is divisible by k if (n % k != 0) { continue; // If not, move to the next k value } int len = n / k; // Calculate the length of each cycle bool flag = true; // Check if all cycles of length 'len' are equal for (int i = 1; i < k; i++) { if (s.Substring((i - 1) * len, len) != s.Substring(i * len, len)) { flag = false; break; } } // If all cycles are equal, return "Yes" if (flag) { return "Yes"; } } // If no k-cycles are found, return "No" return "No"; } static void Main() { int n = 3; string s = "123"; Console.WriteLine(HasKCycles(n, s)); }} |
Javascript
function GFG(n, s) { // Iterate through possible values of // k from 1 to n/2 for (let k = 1; k <= n / 2; k++) { // Check if n is divisible by k if (n % k !== 0) { continue; } // Calculate the length of each substring const len = n / k; let flag = true; // Compare substrings for each segment for (let i = 1; i < k; i++) { // Extract substrings and compare if (s.slice((i - 1) * len, i * len) !== s.slice(i * len, (i + 1) * len)) { flag = false; break; } } // If all substrings match // return "Yes" if (flag) { return "Yes"; } } // If no match is found // return "No" return "No";}function main() { const n = 3; const s = "123"; console.log(GFG(n, s));}// Invoke the main functionmain(); |
Output
Yes
Time Complexity: O(N^2), where N represents the length of the given string.
The time complexity of the program is O(N2) because first it runs a loop for traversing the string and inside that substring function is used.
Auxiliary Space:O(1), because we only need to store a few variables to keep track of the loop variables and the result.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
